Home [BOJ 1339-단어수학] 시간초과 원인(Math.pow가 병목의 원인)
Post
Cancel

[BOJ 1339-단어수학] 시간초과 원인(Math.pow가 병목의 원인)

먼저 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초 이기 때문에 시간이 아슬아슬하게 통과된다. 이 경우 무리하게 백트레킹으로 풀이하려고 하기 보다는 다른 풀이를 생각하는것이 안전하다고 생각한다.

This post is licensed under CC BY 4.0 by the author.

Trending Tags