단어 목록이 주어졌을 때, 각 단어는 그 단어를 구성하는 글자들의 모스 부호를 이어 붙인 형태로 표현할 수 있습니다. 예를 들어 "cba"라는 단어는 "-.-..--..."로 나타낼 수 있으며, 이는 "-.-." + "-..." + ".-"를 연결한 것입니다. 이러한 연결 방식을 단어의 변환(transformation)이라고 부릅니다.
국제 모스 부호(International Morse Code)는 각 영문 글자를 점(.)과 선(-)의 조합으로 매핑하는 표준 인코딩을 정의합니다. 예를 들어 "a"는 ".-", "b"는 "-...", "c"는 "-.-."에 대응됩니다.
알파벳 26개 글자 전체의 모스 부호 목록은 다음과 같습니다.
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
문제 예시
입력이 ["gin", "zen", "gig", "msg"]라면 출력은 2가 됩니다. 각 단어의 변환 결과를 살펴보면 다음과 같습니다.
- "gin" → "--...-."
- "zen" → "--...-."
- "gig" → "--...--."
- "msg" → "--...--."
네 단어 중 실제로 존재하는 서로 다른 변환 결과는 두 가지뿐이므로 정답은 2입니다.
해결 접근 방법
이 문제는 집합(set) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 모든 단어를 모스 부호로 변환한 뒤, 집합에 저장하여 중복을 자동으로 제거하는 것입니다.
- 알파벳 순서대로 정렬된 모스 부호 26개를 morse_codes 리스트에 저장합니다.
- 중복 제거를 위해 빈 집합 s를 생성합니다.
- words의 각 단어에 대해 다음을 반복합니다.
- temp라는 빈 문자열을 초기화합니다.
- 단어의 각 문자 c에 대해 temp에 morse_codes[ord(c) - 97]을 이어 붙입니다. 소문자 'a'의 ASCII 코드가 97이므로, ord(c)에서 97을 빼면 해당 글자의 인덱스를 얻을 수 있습니다.
- 완성된 temp를 집합 s에 추가합니다.
- 집합 s의 크기를 반환합니다. 이것이 곧 서로 다른 모스 부호 변환의 개수입니다.
구현 예제
class Solution: def uniqueMorseRepresentations(self, words): morse_codes = [".-","-...","-.-.","-..",".","..-.","--.", "....","..",".---","-.-",".-..","--","-.", "---",".--.","--.-",".-.","...","-","..-", "...-",".--","-..-","-.--","--.."] s = set() for word in words: temp = '' for c in word: temp += morse_codes[ord(c) - 97] s.add(temp) return len(s) ob = Solution() print(ob.uniqueMorseRepresentations(["gin", "zen", "gig", "msg"]))
입력
["gin", "zen", "gig", "msg"]
출력
2
복잡도 분석
시간 복잡도는 O(S)입니다. 여기서 S는 모든 단어 길이의 총합으로, 각 문자마다 모스 부호를 한 번씩 연결하기 때문입니다. 공간 복잡도 역시 최악의 경우 O(S × M)이며, M은 모스 부호 코드의 평균 길이입니다. 집합을 사용하면 중복 검사 없이도 자동으로 고유한 변환만 남기 때문에 코드가 매우 간결해진다는 점이 이 풀이의 가장 큰 장점입니다.