자바(백준) 1339 단어 수학

오답 노트 & 새로 알게 된 점

문제에서 단어의 개수가 최대 10개, 알파벳 길이는 최대 8이고 서로 다른 문자는 서로 다른 숫자를 나타내기 

때문에 10!로 TLE가 나지 않다고 생각이 들어 백트래킹을 이용하여 풀었다.

 

중복된 알파벳을 제거하기 위해 Set 컬렉션을 사용했고, arr라는 배열에 set의 내용을 그대로 옮겼다.

백트래킹을 이용하여 0~9의 숫자를 possible 배열에 넣어주었다.

이 때, possible의 index는 알파벳을 뜻하고, value는 알파벳에 해당한 숫자였다.

 

findNum 메서드를 사용하여 인자로 string을 보내면

각 자리의 알파벳에 해당하는 숫자를 possible 배열에서 찾아 숫자로 만들어 반환시켜준다.

 

이렇듯 문제를 해결하는데 어려움은 없었다. 그러나 계속 TLE가 났다. 

어느 부분이 잘못된지 전혀 몰랐다. 다른 블로그들을 봐도 백트래킹으로 풀었다.

그래서 하나하나 지우고 쓰는 것을 반복하면서 어느 부분이 TLE를 유발해내는지 찾았다.

바로 Math.pow부분이었다.  처음에는 findNum 메서드에서 string을 int로 변환시킬 때,

1의 자리, 10의 자리를 나타내기 위해 10의 거듭제곱을 Math.pow를 이용했다.

그러나 Math.pow는 O(N)이고, 현재 작성한 코드는 O(1)이다.

 

Math.pow를 작성하지 않으면 TLE가 나지 않아

앞으로 이러한 자릿수를 구현할 때는 이와 같은 O(1) 방법을 사용해야겠다.

이 문제를 가지고 오후를 날리게 되서 절대 까먹지 않을 것 같다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, max = Integer.MIN_VALUE;
    static String A[];
    static boolean visit[] = new boolean[10];
    static int possible[] = new int[26];
    static char arr[];
    static Set<Character> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        input();
        pro();
 
        System.out.println(max);
    }
 
    static void pro() {
        for (int i = 0; i < N; i++) {
            String s = A[i];
            for (int j = 0; j < s.length(); j++) {
                set.add(s.charAt(j));
            }
        }
 
        arr = new char[set.size()];
 
        int idx = 0;
 
        for (char ch : set) {
            arr[idx++] = ch;
        }
 
        dfs(0);
    }
 
    static void dfs(int cnt) {
        if (cnt == set.size()) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                sum += findNum(A[i]);
            }
            max = Math.max(sum, max);
            return;
        }
 
        for (int i = 0; i < 10; i++) {
            if(visit[i]) continue;
 
            visit[i] = true;
            possible[arr[cnt] - 'A'] = i;
            dfs(cnt + 1);
            visit[i] = false;
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new String[N];
 
        for (int i = 0; i < N; i++) A[i] = br.readLine();
    }
 
    static int findNum(String s) {
        int num = 0;
 
        for(int i = 0; i < s.length(); i++){
            num *= 10;
            num += possible[s.charAt(i) - 'A'];
        }
 
        /*
        이 부분으로 코드를 돌리면 틀리게 됨.
        Math.pow(거듭제곱 해주는 얘)가 없으면 맞음. 있으면 틀림
        //O(8 * 8)
        for (int i = 0; i < s.length(); i++) {
            int idx = possible[s.charAt(i) - 'a'];
            if(idx == 0) idx = 1;
            else num += idx * Math.pow(10, s.length() - i - 1);
        }*/
 
        return num;
    }
}