[boj : 1339 ] 단어 수학

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

1339번: 단어 수학

해설 : 전형적인 브루트포스 문제입니다. 모든 가능한 경우의 수를 해보면 되죠.

주어진 문자열을 문자 하나씩 중복되지 않게 순차적으로 0번부터 X번이라고 가정하고 permutation을 돌려주면 됩니다.

전 중복처리를 map 자료구조를 이용해서 해주었습니다.

/*JAVA IO Template Reference : 류호석*/

import javax.xml.crypto.dsig.XMLSignature;
import java.io.*;
import java.lang.reflect.Array;
import java.lang.reflect.ParameterizedType;
import java.nio.charset.StandardCharsets;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    private static FastIO scan = new FastIO();
    //정답은 sb에 append 를 사용하여 출력
    //만약 개행까지 출력하고 싶으면 append('\n')을 추가
    static StringBuilder sb = new StringBuilder();

    static int n,ans;
    static int[] per = new int[10];
    static boolean[] visit = new boolean[10];
    static String[] arr = new String[10];
    static Map<Character,Integer> mp = new HashMap<>();

    public static void main(String[] args) {
        //int t;
        //t = scan.nextInt();
        //while(t-->0){
            solve();
        //}
    }
    public static void solve() {
        int cnt=0;
        n = scan.nextInt();

        for(int i=0;i<n;i++){
            arr[i]=scan.next();
            for(int j=0;j<arr[i].length();j++){
                if(!mp.containsKey(arr[i].charAt(j)))
                    mp.put(arr[i].charAt(j),cnt++);
            }
        }
        dfs(0);
        System.out.println(ans);
    }
    public static void dfs(int depth){
        if(depth==mp.size()){
            int ret=0;
            for(int i=0;i<n;i++){
                int x=0;
                for(int j=0;j<arr[i].length();j++){
                    x*=10;
                    x+=per[mp.get(arr[i].charAt(j))];
                }
                ret+=x;
            }
            ans = max(ans,ret);
            return;
        }
        for(int i=0;i<10;i++){
            if(!visit[i]){
                visit[i]=true;
                per[depth]=i;
                dfs(depth+1);
                per[depth]=0;
                visit[i]=false;
            }
        }
    }
}
class Pair{
    int x,y;
    public Pair(int x,int y){
        this.x=x;
        this.y=y;
    }
}
class FastIO{
    BufferedReader br;
    StringTokenizer st;

    public FastIO(){
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
    Long nextLong(){
        return Long.parseLong(next());
    }
    String nextLine(){
        String str="";
        try{
            str = br.readLine();
        }catch (IOException e){
            e.printStackTrace();
        }
        return str;
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
}