[백준 1339 : JAVA] 단어 수학 / 백트래킹

문제

---

 

 

 

풀이

---

문제를 단순화해보자.

예를 들어, 주어진 문자열이 다음과 같이 2개 주어졌다면

ABC

BCDE

 

위의 문자열에서 사용된 문자는 A B C D E  ---> 5개다.

즉, 0~9까지의 수열에서 5개의 부분수열을 구하는 문제로 바라볼 수 있다. 

입력 문자열과는 별도로 어떤 문자들이 사용되었는지 파악이 필요한데, 아래와 같이 List 자료구조에 하나씩 순차적으로 담는다.

for (int i = 0; i < N; i++) {
    words[i] = br.readLine(); // 입력 문자열 
    for (int j = 0; j < words[i].length(); j++) {
        if (!alpabetList.contains(words[i].charAt(j))) {
            alpabetList.add(words[i].charAt(j));
        }
    }
}

 

위에서 예를 든 문자열이라면, alpabetList에 A B C D E 문자가 순차적으로 저장될 것이다.

이제 부분 수열을 구한 후 하나씩 대입해보면 되는데, 예를 들어, 1 2 3 4 5 라는 부분 수열을 구했다면 순서 그대로 값을 대입해보면서 최종 값을 구한다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, ans = Integer.MIN_VALUE;
    private static String[] words;
    private static List<Character> alpabetList = new ArrayList<>();
    private static int[] val;
    private static boolean[] visited = new boolean[10];

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        words = new String[N];
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();
            for (int j = 0; j < words[i].length(); j++) {
                if (!alpabetList.contains(words[i].charAt(j))) {
                    alpabetList.add(words[i].charAt(j));
                }
            }
        }

        val = new int[alpabetList.size()];

        dfs(0);
        System.out.println(ans);
        br.close();
    }

    private static void dfs(int depth) {
        if (depth == alpabetList.size()) {
            int sum = 0;
            for (int i = 0; i < N; i++) {
                int num = 0;
                for (int j = 0; j < words[i].length(); j++) {
                    num *= 10;
                    num += val[ alpabetList.indexOf(words[i].charAt(j)) ];
                }
                sum += num;
            }
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            val[depth] = i;
            dfs(depth + 1);
            val[depth] = 0;
            visited[i] = false;
        }
    }
}