[JAVA] 백준 1399 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

 

알고리즘 완벽하다고 생각했으나 시간초과가 난 이유는 바로

 

String 연산 때문이다.

 

AB 에서 A=9 이고 B=8 이라고 할 때,  98로 만드는 과정을 아채처럼 할 경우

int answer = 0;
String s = "98";
answer += Integer.parseInt(s);

바로 시간 초과가 나온다.

 

반면 아래처럼 할 경우 시간초과를 피할 수 있다.

int temp = 0;
for(char c : clist){
    temp *= 10;
    temp += c에 해당하는 숫자;
}
sum += temp;

 

메모리가 너무 많이 나오는 경우는 불필요한 선언 부분이 있는지 확인해보자.

 

전체 코드

import java.util.*;
import java.util.stream.Collectors;

class Main{
    static int n;
    static int answer = 0;
    static List<Character> list;
    static int listSize;
    static List<char[]> words = new ArrayList<>();

    static public void main(String[] args){
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            Set<Character> set = new HashSet<>();
            for(int i=0;i<n;i++){
                char[] tmp = sc.next().toCharArray();
                words.add(tmp);
                for(char t : tmp){
                    set.add(t);
                }
            }

            list = set.stream().collect(Collectors.toList());
            listSize = list.size();
            boolean[] visited = new boolean[10];
            int[] results = new int[list.size()];

            dfs(results,0,visited);

        System.out.println(answer);
    }

    static void dfs(int[] results,int idx,boolean[] visited){
        if(idx == listSize){
            int temp = calculate(results);
            if(temp > answer){
                answer = temp;
            }
        }else{
            for(int i=9;i>9-listSize;i--){
                if(visited[i]) continue;
                visited[i] = true;
                results[idx] = i;
                dfs(results,idx+1,visited);
                visited[i] = false;
            }
        }
    }

    static int calculate(int[] results){
        int sum = 0;
        for(char[] clist : words){
            int temp = 0;
            for(char c : clist){
                temp *= 10;
                temp += results[list.indexOf(c)];
            }
            sum += temp;
        }
        return sum;
    }

}