[Leet Code] 804. Unique Morse Code Words

문제 원본: https://leetcode.com/problems/unique-morse-code-words/

문제

국제 모스 부호는 각 문자가 점과 대쉬(“-“)로 이루어진 표준 암호를 말하며 다음과 같다.

• a는 ".-"이다
• b는 "-..."이다
• c는 "-.-."이다.

편의상 영어 알파벳 26글자의 표는 아래와 같이 주어진다.

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

각 문자가 모스 부호의 결합으로 표현될 수 있는 문자열 배열 words가 주어진다.

• 예를 들어 "cab"는 "-.-.", ".-", "-..."를 합친 "-.-..--..."로 표현할 수 있다. 이를 단어의 transformation 결합이라고 할 것이다. 모든 단어들 중에 서로 다른 transformations가 몇 개인지를 반환하라.

Example 1:

Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations: "--...-." and "--...--.".

Example 2:

Input: words = ["a"]
Output: 1

Constraints:

• 1 <= words.length; <= 100
• 1 <= words[i].length <= 12
• words[i]는 소문자로 이루어져 있다.

접근 방법

일단 문제를 보고 반환까지의 단계를 다음과 같이 나눴다.

1. 문자열 배열에서 하나의 문자열을 한 글자씩 쪼갠다.
2. 한 글자씩 모스 부호와 매핑시켜서 변환한다.
3. 모든 글자가 변환되면, 이를 모스 부호 list에 저장한다.
4. 모든 문자열이 변환되면, 모스 부호 list에서 중복을 제거한다.
5. 모스 부호 list의 크기를 반환한다.

우선 문자열 배열에서 문자열을 하나씩, 한 문자열에서 한 글자씩 처리할 것이기 때문에 반복문은 두 개가 필요하다.

한 문자열 내의 글자를 모스 부호와 매핑시켜야 하는데, 이를 아스키 코드 값으로 처리하기로 했다. words[문자열_인덱스][문자_인덱스]의 값은 분명히 char 하나일 것인데, 이는 ‘a’ ~ ‘z’임이 보장된다. 그리고 모스 부호 테이블을 문제에서 제공해줬는데, ‘a’는 0번, ‘b’는 1번의 순서로 정렬되어있다. 따라서 words[문자열_인덱스][문자_인덱스] - 'a'를 함으로써 이를 모스 부호 테이블의 인덱스로 제공한다면, 해당 글자가 모스 부호 테이블을 통해 부호화된 문자열을 얻을 수 있다.
참고로 파이썬은 직접적인 char - char 연산은 안 되는 것 같아서 직접 글자를 ord() 함수로 아스키 코드 값으로 변환한 다음, 97('a'의 아스키 코드 값)을 빼줬다.

부호화된 문자열은 일단 모스 부호 list에 저장할 것이다. 여기서 자바/파이썬과 C#의 풀이가 나뉜다.
자바와 파이썬은 각각 HashSet, Set 자료형이 있기 때문에, 중복된 값은 입력되지 않으므로 서로 다른 모스 부호를 쉽게 구할 수 있다. 파이썬으로는 dict 자료형을 써볼까도 했지만, 26개를 일일이 초기화해주자니 살짝 귀찮았다.
그러나 C#은 내가 알기로는 위와 같은 자료형이 없기 때문에, List 자료형의 Distinct() 메서드를 사용하여 중복 값을 제거할 것이다.

중복 값이 제거되면, 해당 모스 부호 list의 크기를 반환함으로써 서로 다른 모스 부호가 몇 개인지를 반환한다.

풀이

Java

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morseCodes = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
                               "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
                               "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
                               "-.--", "--.."};
        HashSet<String> convertedSet = new HashSet<String>();
        for (int i = 0; i < words.length; i++) {
            char[] charsInWord = words[i].toCharArray();
            String converted = "";
            
            for (int j = 0; j < charsInWord.length; j++) {
                converted += morseCodes[charsInWord[j] - 'a'];
            }
            convertedSet.add(converted);
        }
        return convertedSet.size();
    }
}

• Runtime: 2ms
• Memory: 40.3MB

C#

public class Solution {
    public int UniqueMorseRepresentations(string[] words) {
        String[] morseCodes = {".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
                               "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
                               "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
                               "-.--", "--.."};
        List<String> convList = new List<String>();
        for (int i = 0; i < words.Length; i++)
        {
            char[] charsInWord = words[i].ToCharArray();
            String converted = "";
            
            for (int j = 0; j < charsInWord.Length; j++)
            {
                converted += morseCodes[charsInWord[j] - 'a'];
            }
            convList.Add(converted);
        }
        convList = convList.Distinct().ToList();
        return convList.Count;
    }
}

• Runtime: 76ms
• Memory: 39.5MB

Python

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        morseCodes = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....",
                      "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.",
                      "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
                      "-.--", "--.."]
        convertedSet = set()
        for i in range(len(words)):
            converted = ""
            
            for j in range(len(words[i])):
                converted += morseCodes[ord(words[i][j]) - 97]
            convertedSet.add(converted)
        return len(convertedSet)

• Runtime: 36ms
• Memory: 13.9MB