[백준]1339: 단어 수학 - JAVA

[백준]1339: 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

풀이

백트랙킹을 사용하여 풀었다. 먼저 알파벳을 리스트에 중복 없이 저장한 다음, 0부터 숫자를 하나씩 올리며 알파벳에 숫자를 할당(?)해 주었다.

 

리스트의 길이만큼 숫자를 다 뽑았다면 원래의 문자열과 비교하여 자리수에 맞게 숫자 연산을 하여 MAX값을 찾아주었다.

 

풀이 코드의 구조를 보면 전형적인 백트랙킹 순열 문제와 같다. 이번 문제에서 어려웠던 부분은 문자열을 자리수에 맞게 숫자 연산을 하는 부분이었다. 이 부분을 제외하면 그렇게 어렵지 않은 문제였당

 

코드

import java.util.*;
 
public class Main {
    
    static int n;
    static int max = Integer.MIN_VALUE;
    static ArrayList<Character> list;
    static String[] word;
    static boolean[] visited;
    static int[] value;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        list = new ArrayList<>();
        word = new String[n];
        
        scan.nextLine();
        for(int i = 0; i < n; i++) {
            word[i] = scan.nextLine();
            for(int j = 0; j < word[i].length(); j++) {
                if(!list.contains(word[i].charAt(j))) list.add(word[i].charAt(j));
            }
        }
        
        visited = new boolean[10];
        value = new int[list.size()];
        
        backtracking(0);
        System.out.println(max);
    }
    
    public static void backtracking(int len) {
        if(len == list.size()) {
            int sum = 0;
            for(int i = 0; i < n; i++) {
                int num = 0;
                for(int j = 0; j < word[i].length(); j++) {
                    num *= 10;
                    num += value[list.indexOf(word[i].charAt(j))];
                }
                sum += num;
            }
            max = Math.max(max, sum);
            return;
        }
        
        for(int i = 0; i <= 9; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                value[len] = i;
                backtracking(len + 1);
                visited[i] = false;
                value[len] = 0;
            }
        }
    }
}