먼저 accept된 코드를 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int getSum(Deque<Character> perm){
HashMap<Character,Integer> valueMap = new HashMap<>();
int cur = 9;
Iterator<Character> iter = perm.iterator();
while (iter.hasNext()){
valueMap.put(iter.next(),cur--);
}
int res = 0;
for (String s : input) {
int mult = 1;
for (int i = s.length()-1; i > -1; i--) {
char ch = s.charAt(i);
res += mult * valueMap.get(ch);
mult *= 10;
}
}
return res;
}
다음은 시간초과가난 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int getSum(char[] perm) {
int cur = 9;
for (char ch : perm) {
hashMap.put(ch,cur--);
}
int res = 0;
for (String s : input) {
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
res += Math.pow(10, s.length() - 1 - i) * hashMap.get(ch);
}
}
return res;
}
최대 8자리수의 합을 구할때 빠른버전의 경우 최대 8번의 반복문을 돈다. 느린버전의 경우 Math.pow 내부에서 지수부분만큼 반복문을 돌게되므로 1+2+3+4+…+8 = 36번 돌게 된다. 위 문제를 백트레킹 방식으로 풀이할경우, 빠른버전의 경우 시간 복잡도는 10! * (810)8이 되고 느린버전의 경우 시간 복잡도는 10! * (810)36이 된다. 시간 제한이 2초 이기 때문에 시간이 아슬아슬하게 통과된다. 이 경우 무리하게 백트레킹으로 풀이하려고 하기 보다는 다른 풀이를 생각하는것이 안전하다고 생각한다.