[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; <= 1001 <= words[i].length <= 12words[i]는 소문자로 이루어져 있다.
접근 방법
일단 문제를 보고 반환까지의 단계를 다음과 같이 나눴다.
- 문자열 배열에서 하나의 문자열을 한 글자씩 쪼갠다.
- 한 글자씩 모스 부호와 매핑시켜서 변환한다.
- 모든 글자가 변환되면, 이를 모스 부호 list에 저장한다.
- 모든 문자열이 변환되면, 모스 부호 list에서 중복을 제거한다.
- 모스 부호 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
댓글남기기