[BOJ] 1339. 단어수학

상당히 많은 시간을 투자했던 문제이다.

우선 간단하게 N의크기가 10이하인것을 보고 백트래킹으로 접근하려했다. 하지만 최악의 경우가 10!정도가 나오는데 이것 말고도 안쪽에서의 String 연산때문에 시간초과를 해결할 수 없었다. 그래서 StringBuilder를 사용하여 결국 문제는 해결하였지만 최악의 시간복잡도를 가지고 해결하게 된 셈이 되었다. 아래가 다음 코드이다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedHashSet;
import java.util.Set;
 
public class Main_bj_1339_단어수학 {
 
    static int inputNum;
    static String[] input;
    
    static Set<Character> set;
    
    static int alpNum;
    static int[] numbers;
    static int[] arr;
    static boolean[] visit;
    static char[] alp;
    
    static int max;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        inputNum=Integer.parseInt(br.readLine());
        
        
        set=new LinkedHashSet<>();
        input=new String[inputNum];
        for(int i=0;i<inputNum;i++) {
            String str=br.readLine();
            input[i]=str;
            for(int j=0;j<str.length();j++) {
                set.add(str.charAt(j));
            }
        }
        
        alpNum=set.size();
        
        numbers=new int[alpNum];        //9부터 숫자저장
        int start=9;
        for(int i=0;i<alpNum;i++) {
            numbers[i]=start--;
        }
        
        arr=new int[alpNum];            //숫자 순서
        visit=new boolean[alpNum];        //방문 체크
        alp=new char[alpNum];            //알파벳 저장
        
        int index=0;
        for(char c : set) {                //알파벳 저장
            alp[index++]=c;
        }
        
        max=Integer.MIN_VALUE;
        perm(0);
        
        System.out.println(max);
    }
    
    static void perm(int depth) {
        if(depth==alpNum) {
            int sum=0;
            for(int i=0;i<inputNum;i++) 
                sum+=convert(input[i]);
            max=Math.max(max, sum);
            return;
        }
        
        for(int i=0;i<alpNum;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                arr[depth]=numbers[i];
                perm(depth+1);
                visit[i]=false;
            }
        }
    }
 
    static int convert(String string) {
        
        StringBuilder sb = new StringBuilder();
        
        int n=0;
        int size=string.length();
        for(int i=0;i<string.length();i++) {
            char c = string.charAt(i);
            for(int j=0;j<alpNum;j++) {
                if(c==alp[j]) {
                    sb.append(arr[j]);
                    break;
                }
            }
        }
        return Integer.parseInt(sb.toString());
    }
}
 

 

문제를 해결하긴 하였지만 남들과 시간이나 메모리를 비교해보았을 때 최악의 효율을 보였기에 다른 방법을 생각해보았다. 즉 위에서처럼 모든 경우를 다 보는 것 말고, 알파벳의 갯수만큼 배열을 하나 잡고 해당하는 해당하는 자릿수만큼 가중치를 주는 방식을 반복해보았다. 그후 배열을 정렬후 가장 큰것부터 9부터 하나씩 줄여주면 할당시켜주어서 답을 구하였다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main_bj_1339_단어수학_2 {
    
    static int[] arr;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        
        arr=new int[26];
        
        for(int i=0;i<N;i++) {
            String num=br.readLine();
            int value=(int)Math.pow(10, num.length()-1);
            
            for(int j=0;j<num.length();j++) {
                char c=num.charAt(j);
                arr[c-'A']+=value;
                value/=10;
            }
            
        }
        
        Arrays.sort(arr);
        
        int index=9;
        int answer=0;
        for(int i=25;i>=0;i--) {
            if(arr[i]==0)
                break;
            answer+=arr[i]*index--;
        }
    
        System.out.println(answer);
    }
}