[LeetCode] 804. Unique Morse Code Words

https://leetcode.com/problems/unique-morse-code-words/

Unique Morse Code Words - LeetCode

 

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

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

 

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cba" can be written as "-.-..--...", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

 

해석

각 문자가 일련의 점과 선으로 매핑되는 국제 모스 코드의 표준 인코딩 방식이 아래와 같이 정의 되어있다

"a" -> ".-" , "b" -> "-..." , "c" -> "-.-."

편의상 영어 알파벳 26 자의 전체 표가 아래에 나와 있다.

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

 

이제 단어 목록이 주어지면 각 단어는 각 문자의 모스 부호를 연결 한 것으로 쓸 수 있다.

예를 들어 "cba"는  "-.-..--..." 로 쓸 수 있다("-.-." + "-..." + ".-"). 

우리는 그러한 연결을 단어의 변형(transformation of a word)이라고 부를 것입니다.

 

우리가 가지고있는 모든 단어들 사이의 다양한 변형의 수를 반환하시오.

 

Example

Input: words = ["gin", "zen", "gig", "msg"]

Output: 2

Explanation:

각 단어의 변형은 아래와 같다 :

"gin" -> "--...-."

"zen" -> "--...-."

"gig" -> "--...--."

"msg" -> "--...--."

서로 다른 변형은 "--...-." 와 "--...--." 총 2개다.

 

사전지식

Set 컬렉션

• 같은 요소의 중복을 허용하지 않는다
• TCP School - Set 컬렉션 클래스[Link] 글 참고

 

솔루션 Solution

class Solution {
    
    //모스부호 변환용
    public static String[] mosMap = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    public int uniqueMorseRepresentations(String[] words) {
    
    	// 중복 요소를 배제해기위해 Set을 사용함
        Set<String> mosSet = new LinkedHashSet<>();
        
        for(String str : words){
        
          StringBuilder builder = new StringBuilder();
            for(char c : str.toCharArray()){
            	
                // 모스부호로 변환
                builder.append(mosMap[c - 'a']);
            }
            
            // 변환된 모스부호는 String 형태로 Set 컬렉션에 저장
            // 만약 동일한 모스부호가 저장되어 있었다면, 새로 추가되지 않는다.
            // 즉, Set 컬렉션에는 서로 다른 모스부호만 저장되어 있다.
            mosSet.add(builder.toString());
      }  
      
      // 서로 다른 모스부호의 개수 반환
      return mosSet.size();  
    }
}

 

주어진 단어를 모스부호로 변환하는 방법은 간단하니 설명하지 않고 넘어가겠다.

문제의 핵심은 다른 모습의 모스부호의 개수를 알아내는 것인데, 같은 요소의 중복을 허용하지 않는 Set 컬렉션을 사용하면 쉽게 해결 가능하다.

모스부호로 변환 후, 모스부호를 Set에 저장하는데, 만양 동일한 모스부호가 이미 Set 컬렉션에 저장되어 있다면, 중복으로 저장되지않는다.

즉, 각기 다른 모스부호만 Set 컬렉션에 저장된다.

 

결과적으로 모스부호로의 변환이 모두 완료 된 후, Set 컬렉션에 저장된 문자열이 서로 다른 모습의 모스부호이며, 그 개수를 최종 반환하면 된다.