백준 1339. 단어 수학 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/1339

"수학적 접근 혹은 백트래킹"

나는 수학적으로 접근하지 못하고, 백트래킹을 이용했다. 그래서 실행 시간이 오지게 길었다. 그래도 돌긴 도는구나.. Set을 쓰면 더 좋을 것 같은데 iterator 구현이 익숙치 않아서 리스트에서 contains 체크를 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class Main {
    
    static int n;
    static List<Integer> list = new ArrayList<>();
    static int[] values;
    static char[][] words;
    static boolean[] visited = new boolean[10];
    static int max;
    static int size;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        
        words = new char[n][];
        
        for (int i = 0; i < n; i++) {
            words[i] = br.readLine().toCharArray();
            for (int j = 0; j < words[i].length; j++) {
                if(!list.contains(words[i][j]-65)) {
                    list.add(words[i][j] - 65);
                }
            }
        }
        size = list.size();
        values = new int[list.size()];
        
        solve(0,0);
        System.out.println(max);
    }
    
    static void solve(int idx, int cnt) {
        if(size == cnt) {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int num = 0;
                for (int j = 0; j < words[i].length; j++) {
                    num *= 10;
                    num += values[list.indexOf(words[i][j]-65)];
                }
                sum += num;
            }
            max= Math.max(max, sum);
            return ;
        }
        
        for (int i = 9; i >= 0; i--) {
            if(visited[i])
                continue;
            
            visited[i] = true;
            values[idx] = i;
            solve(idx+1,cnt+1);
            values[idx] = 0;
            visited[i] = false;
        }
    }
}