[LeetCode] #804. Unique Morse Code Words

문제 :

 

예시)

 

문제는 간단하다. a부터 z까지의 알파벳에 대응하는 모스부호 코드가 주어지고, 입력값으로 문자열들을 담은 리스트가 주어지면, 각 요소의 문자열을 모스 부호로 변환하여 중복되지 않는 모스 부호의 갯수를 리턴하면 된다. 위의 예시에서 보이듯, gin, zen, gig, msg의 단어들중 gin, zen과 gig, msg의 모스부호는 짝을 이뤄 중복되어 이 경우에는 2를 리턴한다. 

 

먼저, 이 문제에서 중요한 것이 두가지 있다.

 

1. 각각의 서로 다른 알파벳은 서로 다른 모스 부호와 매핑된다 => 그렇다면, 키-값 쌍을 지을 수 있는 해시 테이블을 이용한다. 만약 우리가 z에 담긴 모스 부호를 찾고싶다고 한들 a-z까지 선형 검색을 할 필요가 없어 O(1)의 실행시간으로 검색을 할 수 있는 장점이 있다. 이 문제에서는 어떤 알파벳이 어떤 모스부호에 대응하는지를 찾는게 주 목적이므로 검색에 가장 빠른 시간이 소요되는 해시 테이블을 이용했다.

 

2. 결국 리턴하고자 하는 값은 "중복되지 않는" 모스 부호의 갯수이다. 그렇다면 중복을 허용하지 않는 자료구조인 집합을 선언하고, 반복문을 돌며 집합에 모스 부호들을 담아준 후, 마지막엔 이 집합의 길이를 리턴하면 된다.

 

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        dicti = {'a':".-", 'b':"-...", 'c':"-.-.", 'd':"-..", 'e':".", 'f':"..-.", 'g':"--.", 'h':"....", 'i':"..", 'j':".---", 'k':"-.-", 'l':".-..", 'm':"--", 'n':"-.", 'o':"---", 'p':".--.", 'q':"--.-", 'r':".-.", 's':"...", 't':"-", 'u':"..-", 'v':"...-", 'w':".--", 'x':"-..-", 'y':"-.--", 'z':"--.."}

        moreSet = set()
        

        for word in words:
            morse = ""
            for i in word:
                morse += dicti.get(i)
            moreSet.add(morse)

        return len(moreSet)

 

- 엄청 간단하다. 먼저, 모스부호들을 먼저 딕셔너리에 담아야 한다(이 문제에선 이게 제일 오래 걸렸다.)

- 그 다음, 위에서 언급한 모스 부호들을 담아줄 집합을 선언한다.

- 입력값으로 주어진 words라는 문자열이 담긴 리스트를 순회한다.

           - 새로운 단어로 바뀔 때마다, 그 단어의 모스 부호들을 담을 morse라는 변수를 ""로 초기화 해 준다.

           - for i in word:를 통해 각 단어의 알파벳을 하나씩 가져와 dict1.get(i)를 통해 딕셔너리에서 그 문자에 해당하는 모스 부호를 검색

           하고, 이전에 선언한 morse부호에 담아준다. 여기서 주의 할 점은 파이썬의 문자열은 불변의 객체이기 때문에 리스트에서 사용하는 

           .append()를 사용할 수 없다. 문자열에 새로운 문자를 추가하려면 문자열 연결(concatenation)을 사용해야 한다. 
           - 한 단어의 모든 철자 검색을 마친 후, 그 모스 부호를 위에서 선언한 빈 집합에 담아준다.(여기서 모스 부호가 중복 된다면 어차피

            집합에 담기지 않을 것이다.)

           - 마지막으로, 우리가 원하는 값인 집합의 길이를 리턴 하고 함수를 끝낸다.