프로그래머스 입문 120838 모스부호 1
문제
문자열 letter가 매개변수로 주어진다.
이 문자열은 모스 부호로 이루어져 있으며, 각 모스 부호는 공백으로 구분된다.
각 모스 부호를 영어 소문자로 변환한 문자열을 반환하시오.
| letter | result |
|---|---|
| “…. . .-.. .-.. —” | “hello” |
| “.–. -.– - …. — -.” | “python” |
풀이
배열을 이용해 해석하기
#include <stdlib.h>
#include <string.h>
char* solution(const char* letter)
{
const char* morse_codes[26] = {
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."
};
size_t len = strlen(letter);
char* buffer = (char*)malloc(len + 1);
char* result = (char*)malloc(len + 1);
int result_index = 0;
strcpy(buffer, letter);
char* token = strtok(buffer, " ");
while (token != NULL)
{
for (int i = 0; i < 26; i++)
{
if (strcmp(token, morse_codes[i]) == 0)
{
result[result_index++] = 'a' + i;
break;
}
}
token = strtok(NULL, " ");
}
result[result_index] = '\0';
free(buffer);
return result;
}모스 부호 26개를 알파벳 순서대로 morse_codes 배열에 담아 둔다.
strtok는 문자열을 직접 수정하면서 토큰을 나누므로, const 매개변수인 letter를 그대로 사용할 수 없다.
그래서 letter를 buffer에 복사한 뒤, 공백을 기준으로 토큰을 하나씩 가져온다.
각 토큰을 morse_codes 배열의 원소와 차례대로 비교하고, 같은 모스 부호를 찾으면 그때의 인덱스 i를 이용한다.
morse_codes 배열이 알파벳 순서로 정렬되어 있으므로, 인덱스 i는 'a'로부터 떨어진 거리, 즉 오프셋(offset)이 된다.
따라서 'a' + i로 실제 영어 소문자를 구해 result 문자열에 저장한다.
이진 트리를 이용해 해석하기
#include <stdlib.h>
#include <string.h>
char* solution(const char* letter)
{
char tree[32] = { 0 };
const char* morse_codes[26] = {
".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
"..-", "...-", ".--", "-..-", "-.--", "--.."
};
for (int i = 0; i < 26; i++)
{
int index = 1;
for (int j = 0; morse_codes[i][j] != '\0'; j++)
{
char signal = morse_codes[i][j];
if (signal == '.')
{
index *= 2;
}
else
{
index = index * 2 + 1;
}
}
tree[index] = 'a' + i;
}
size_t len = strlen(letter);
char* result = (char*)malloc(len + 1);
int result_index = 0;
int index = 1;
for (int i = 0; letter[i] != '\0'; i++)
{
char signal = letter[i];
if (signal == ' ')
{
result[result_index++] = tree[index];
index = 1;
}
else if (signal == '.')
{
index *= 2;
}
else
{
index = index * 2 + 1;
}
}
result[result_index++] = tree[index];
result[result_index] = '\0';
return result;
}모스 부호는 .와 - 두 가지 신호만 사용한다.
가장 짧은 모스 부호는 .(e)와 -(t)이다.
가장 긴 모스 부호의 길이는 4이고, 그중 일부는 -...(b)와 -.-.(c)이다.
영어 소문자는 26글자다.
루트를 깊이 0으로 보면 깊이 4까지의 노드 수는 2^5 - 1인 31개다.
따라서 깊이 4까지 있으면 26개의 알파벳을 표현하기에 충분하다.
depth 0: root 1 node
/ \
depth 1: .(e) -(t) 2 nodes
/ \ / \
depth 2: ..(i) .-(a) -.(n) --(m) 4 nodes
/ \ / \ / \ / \
depth 3: ...(s) ..-(u) .-.(r) .--(w) more 8 nodes
/ \ / \ / \ / \
depth 4: ....(h) ...-(v) ..-.(f) .-..(l) more 16 nodes
total nodes: 1 + 2 + 4 + 8 + 16 = 31.은 왼쪽, -는 오른쪽으로 이동한다고 보겠다.
".-"은 왼쪽으로 한 번 이동한 뒤 오른쪽으로 한 번 이동한 위치다.
"-.."는 오른쪽으로 한 번 이동한 뒤 왼쪽으로 두 번 이동한 위치다.
따라서 부호가 한 글자 길어질 때마다 트리에서 한 단계 더 내려간다.
이 구조를 배열로 옮기면 경로를 따라 인덱스를 계산하고, 그 위치의 문자를 꺼내면 된다.
이 코드에서는 루트를 1번 인덱스에 두고, 왼쪽 자식을 index * 2, 오른쪽 자식을 index * 2 + 1로 계산한다.
가장 깊은 노드의 인덱스가 31이므로, tree의 크기는 32로 잡는다.
초기화 단계에서는 알파벳 순서로 저장된 morse_codes를 하나씩 읽어 각 문자가 들어갈 위치를 미리 채운다.
예를 들어 r의 모스 부호인 ".-."는 루트 인덱스 1에서 시작한다.
첫 번째 .를 읽으면 왼쪽 자식인 2로 이동하고, 다음 -를 읽으면 오른쪽 자식인 5로 이동한다.
마지막 .를 읽으면 다시 왼쪽 자식인 10으로 이동하므로, 문자 r은 tree[10]에 저장된다.
이 과정을 모든 모스 부호에 대해 반복하면, 각 알파벳이 배열의 알맞은 인덱스에 저장된다.
이제 입력 문자열 letter를 처음부터 순회한다.
문자가 .이면 왼쪽 자식 인덱스로 이동하고, -이면 오른쪽 자식 인덱스로 이동한다.
공백을 만나면 모스 부호 하나가 끝났다는 뜻이므로, tree의 현재 인덱스에 저장된 문자를 result에 추가한다.
그리고 다음 모스 부호를 해석하기 위해 인덱스를 다시 루트인 1로 되돌린다.
문자열의 마지막에는 공백이 없으므로, 마지막 모스 부호는 인덱스만 계산된 채 반복문이 끝난다.
그래서 반복문이 끝난 뒤 현재 인덱스가 가리키는 문자를 result에 추가한다.