[코딩연습] Unique Morse Code Words 고유한 모스부호 가짓수

LeetCode 문제 중 난이도 Easy인 Unique Morse Code Words 이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제 해석

국제 모스 부호는 다음과 같이 각 알파벳 문자가 일련의 점과 대시에 매핑되는 표준 인코딩을 정의한다.

"a"는 ".-", "b"는 "-...", "c"는 "-.-." 등등..

편의를 위해서 알파벳 전체 26문자의 표는 아래를 참고한다.

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

주어진 단어들의 리스트에서 각 단어들은 각각의 알파벳의 모스부호를 연결해서 쓰여질 수 있다. 예를 들어 "cba"는 "-.-." + "-..." + ".-"인 "-.-.-....-"가 된다. 이렇게 이어진것을 단어 변환이라고 부른다. words중에서 그런 서로 다른 변환의 가짓수를 리턴하라.

* 원본문제의 모스부호 변환 예시가 살짝 틀렸는데 그냥 무시하면 된다. 어쨌든 입력값 words을 모스부호로 변환시 나오는 가짓수를 리턴하면 된다.

이 문제는 그냥 직관적으로 풀면 된다. 단어를 모스부호로 나타냈을 때 나올 수 있는 경우의수가 몇가지인지 알기 위해서는 먼저 input으로 받은 words를 모스부호 문자표를 이용해서 변환해야 한다. 그 다음 변환된 결과들 중에서 중복을 제거한 후 총 나오는 가짓수가 몇개인지 세면 된다.

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
                            "-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        //모스부호화 된 words를 저장할 배열
        String[] encoded = new String[words.length];
        
        //알파벳을 모스부호로 치환함
        for(int i=0 ; i<words.length ; i++){
            for(int j=0 ; j<words[i].length() ; j++){
                encoded[i]=encoded[i]+morse[words[i].charAt(j)-'a'];
            }
        }
        
        //중복값을 제거하기 위해 Set에 담는다
        Set<String> codeSet = new HashSet<>();
        for(int i=0 ; i<encoded.length ; i++){
            if(!codeSet.contains(encoded[i])) codeSet.add(encoded[i]);
        }
        
        return codeSet.size();
    }
}

encoded라는 새로운 배열을 생성해서 words의 단어들을 모스부호화 시켜 저장했다. 그 다음 words를 Set 자료형에 담아 중복값을 제외한다. 마지막으로 Set의 사이즈를 리턴하면 된다. 

12번째줄의 words[i].charAt(j)-'a' 는 알파벳의 아스키코드를 이용한 것이다. 알파벳의 모스부호가 morse배열에 a부터 z까지 순서대로 들어가 있으므로 해당 알파벳-'a'를 하면 그 알파벳이 a부터 몇 번째 뒤에 있는지 알 수 있다. 지난번에 풀었던 Valid Anagram 문제의 두번째 풀이와 같은 원리이다.

2019/04/09 - [프로그래밍문제풀기] - [코딩연습] Valid Anagram 유효한 애너그램인지 체크하기

위 코드의 시간복잡도는 O(S), 공간복잡도는 O(S)이다. 여기서 S는 input인 words배열에 들어있는 단어들의 길이의 합을 말한다.

문제 출처 - https://leetcode.com/problems/unique-morse-code-words/