[BOJ] 백준 [1339] 단어 수학JAVA

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

1339번: 단어 수학

문제

풀이

수학적으로 더 쉽게 풀 순 있지만 , 완전탐색 그리디를 연습중이므로 완전탐색으로 접근하였다.
주어진 단어들의 알파벳들이 몇 가지인지 리스트에 저장.
알파벳에 0~9 까지의 숫자들을 완전탐색으로 매핑

탐색이 진행될때마다 depth 카운트를 하나씩 증가시키면서
주어진 단어의 길이와 depth가 같아질 때 탐색을 그만하고 계산해서 제일 높은 값이 나오면 끝

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static ArrayList<Character> list = new ArrayList<Character>();
    static String[] input;
    static boolean[] visit;
    static int[] value;
    static int N,max;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = new String[N];
        for(int i=0;i<N;i++) {
            input[i] = br.readLine();
            for (char c : input[i].toCharArray())
                if(!list.contains(c)) list.add(c);
        }
        visit = new boolean[10];
        value = new int[list.size()];
        dfs(0);
        System.out.println(max);
    }
 
    private static void dfs(int depth) {
        if(depth==list.size()){
            int sum=0;
            for(int i=0;i<input.length;i++){
                int num=0;
                for(int j=0;j<input[i].length();j++){
                    num*=10;
                    num+=value[list.indexOf(input[i].charAt(j))];
                }
                sum+=num;
            }
            max = Math.max(max,sum);
            return;
        }
 
        for(int i=0;i<=9;i++){
            if(visit[i]) continue;
            visit[i]=true;
            value[depth]=i;
            dfs(depth+1);
            value[depth]=0;
            visit[i]=false;
        }
    }
}

참고

0부터 9까지 차례대로 매핑 완전탐색을 하나 , 9부터 차례대로 완전탐색을 하나

시간복잡도 차이가 나지않는다.