(25.01.09)
-
문제 이해
휴대전화 천지인 영어 기준으로 주어진 숫자를 통해 입력할 수 있는 알파벳 배열의 모든 경우의 수를 리스트로 리턴하는 간단한 문제이다. -
문제 풀이
성능을 생각하면 아스키 코드를 이용하면 좋을 듯 하다. 또 결과를 하나의 문자열로 만든 후 digits 크기만큼 split해서 반환하면 좋을 듯 하다. 그런데, 몇몇 숫자는 4개의 문자를 가지므로 아스키 코드를 사용하는 것 보다 단순 dictionary를 만드는게 좋아보인다.
public List<String> letterCombinations(String digits) {
HashMap<Character, char[]> num_to_alpha=new HashMap<Character, char[]>();
num_to_alpha.put('2', new char[]{'a', 'b', 'c'});
num_to_alpha.put('3', new char[]{'d', 'e', 'f'});
num_to_alpha.put('4', new char[]{'g', 'h', 'i'});
num_to_alpha.put('5', new char[]{'j', 'k', 'l'});
num_to_alpha.put('6', new char[]{'m', 'n', 'o'});
num_to_alpha.put('7', new char[]{'p', 'q', 'r', 's'});
num_to_alpha.put('8', new char[]{'t', 'u', 'v'});
num_to_alpha.put('9', new char[]{'w', 'x', 'y', 'z'});
List<String> result=new ArrayList<>();
int total_of_cases=digits.length()==0?0:1;
for(char digit: digits.toCharArray()){
total_of_cases*=num_to_alpha.get(digit).length;
}
System.out.println("total_of_cases: "+total_of_cases);
int length=digits.length();
for(int i=0; i<total_of_cases; i++){
result.add("");
}
for(int i=0; i<length; i++){
char digit=digits.charAt(i);
char[] cases=num_to_alpha.get(digit);
for(int j=0; j<total_of_cases; j++){
String prev_result=result.get(j);
result.set(j, prev_result.concat(String.valueOf(cases[j%(cases.length)])));
}
}
return result;
}
순서도 규칙대로 지켜야하나보다.
약간 BFS의 느낌이 나기도 하고..
(25.01.12)
지난번에 작성한 코드에서 결과의 순서를 문제 규칙대로 리팩토링해야했다.
간단하게 sort로 정렬을 하여 규칙을 맞추어 보려했는데 확인해보니 기존의 코드도 제대로된 경우를 계산하지 못하고 ad ad ad처럼 중복된 결과를 내보내고 있다는 것을 발견했다.
처음부터 로직을 새로 작성해야하는데, 어떻게 해야 가장 최적으로 값을 설정할 수 있을까? 무작정 접근하기에는 까다로운 문제같다.
우선 현재 해결해야하는 테스트 케이스는 다음과 같다.
위 케이스는 약간의 규칙성이 있기에, 보다 나은 케이스를 직접 만들어보자.
Input: digits = "95"
Output: ["wj", "wk", "wl", "xj", "xk", "xl", "yj", "yk", "yl", "zj", "zk", "zl"]
가장 직관적인 방법은 각각의 원소 digit 루프별로 한 글자씩 쌓아가는 것이다. 이 때 고려해야하는 점은 하나의 숫자가 3개 혹은 4개의 알파벳으로 매칭된다는 점이다.
이 때 추가적으로 궁금한 점은 Input: digits="234"처럼 3글자를 넘어가면 Output의 순서가 어떻게 될까? 현재 테스트 케이스의 정렬 규칙은 오름차순을 따르고 있다. 이 순서를 생각하며 결과를 만들기보다는 가장 직관적인 방법으로 모든 경우를 구한 뒤에 정렬하는 방법이 좋아보인다.(이 경우 나중에 TLE가 발생하도록 문제 성격 상 유도할 것 같긴 하다만..)
가장 직관적인 방법은 for(digits[0]){ {for(digits[1]} }처럼 접근하여 알아서 쌓이게끔 하는 것이지만, for이 digits.length()에 의존되어 for문으로는 해결하지 못한다는 문제가 있다.
바뀌는 수가 너무 많으니 고정된 것을 생각해보자. 자리수 마다 가능한 문자는 정해져있다. 또한 총 경우의 수도 정해져있다. 어라? digits의 길이는 최대 4로 정해져있기에 for루프만을 이용해 처리가 가능할 듯 하다.
switch를 이용해 해결했는데 통과하였다.
class Solution {
public List<String> letterCombinations(String digits) {
// 숫자에 매칭되는 알파벳으로 변환하기 위한 룩업 테이블
HashMap<Character, char[]> num_to_alpha=new HashMap<Character, char[]>();
num_to_alpha.put('2', new char[]{'a', 'b', 'c'});
num_to_alpha.put('3', new char[]{'d', 'e', 'f'});
num_to_alpha.put('4', new char[]{'g', 'h', 'i'});
num_to_alpha.put('5', new char[]{'j', 'k', 'l'});
num_to_alpha.put('6', new char[]{'m', 'n', 'o'});
num_to_alpha.put('7', new char[]{'p', 'q', 'r', 's'});
num_to_alpha.put('8', new char[]{'t', 'u', 'v'});
num_to_alpha.put('9', new char[]{'w', 'x', 'y', 'z'});
List<String> result=new ArrayList<>();
switch(digits.length()){
case 0:
return result;
case 1:
for(char c: num_to_alpha.get(digits.charAt(0)))
result.add(String.valueOf(c));
return result;
case 2:
for(char c: num_to_alpha.get(digits.charAt(0)))
for(char c2: num_to_alpha.get(digits.charAt(1)))
result.add(String.valueOf(c).concat(String.valueOf(c2)));
break;
case 3:
for(char c: num_to_alpha.get(digits.charAt(0)))
for(char c2: num_to_alpha.get(digits.charAt(1)))
for(char c3: num_to_alpha.get(digits.charAt(2)))
result.add(String.valueOf(c).concat(String.valueOf(c2)).concat(String.valueOf(c3)));
break;
case 4:
for(char c: num_to_alpha.get(digits.charAt(0)))
for(char c2: num_to_alpha.get(digits.charAt(1)))
for(char c3: num_to_alpha.get(digits.charAt(2)))
for(char c4: num_to_alpha.get(digits.charAt(3)))
result.add(String.valueOf(c).concat(String.valueOf(c2)).concat(String.valueOf(c3)).concat(String.valueOf(c4)));
break;
default:
System.out.println("ERROR");
break;
}
return result;
}
}
