백준 1339 단어 수학 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1339

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int[] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        nums = new int[26]; //각각의 알파벳이 몇개 나왔는지 (자릿수 반영)
        //(ex - bcd -> 100b + 10c + d 이므로, 각각  알파벳 -'A' += 해줄 예정)

        for(int i = 0 ; i < N ; i++) {
            makeInt(br.readLine());
        }

        Arrays.sort(nums);

        int i = 0;
        int answer = 0;
        while(true) {
            int a = nums[25 - i];
            if(a == 0) break;
            answer += a * (9-i);
            i++;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();

    }

    static void makeInt(String s) { //주어진 모든 단어 돌리면, nums에 저장.
        char[] arr = s.toCharArray();
        int index = 1;
        for(char c : arr) {
            nums[c - 'A'] += Math.pow((double) 10, (double) arr.length - index);
            index++;
            //(ex - bcd -> 100b + 10c + d 이므로, 각각  알파벳 -'A' += 100b 이런식으로.)
        }
    }


}

이 문제에서 핵심 로직은 다음과 같다.
ABC -> 100A + 10B + C
BBDES -> 10000B + 1000B +100D + 10E + S
EEDD -> 1000E + 100E + 10D + D
즉, 주어진 String들의 위치에 따라 해당 자릿수의 값을 부여한 후,
한꺼번에 모아준다.

바로 위의 세 String으로 예시를 들면,
배열 nums에 알파벳에 따라 (해당 알파벳 - 'A') 몇개인지 합쳐준다
(A = 100개, B = 11010개, C = 1개, D = 111개, E = 1110개, S = 1개)
해당 개수로 오름차순 정렬을 한 다음,
많이 나온 알파벳부터 9를 할당시켜준다.

B에 9 할당 -> 11010 x 9
E에 8 할당 -> 1110 x 8
D에 7 할당 -> 111 x 7
A에 6 할당 -> 100 x 6
C, S에 각각 5 할당 -> 1x5, 1x5

위를 전부 더한 값
109357이 정답이다.

즉, 많이 나온 알파벳 순서대로 큰 한자릿수 값(9, 8, 7, ...)을 할당해주는
그리디 알고리즘 문제이다.

이렇게 보면 이해하기 어렵지 않은 그리디 알고리즘이다.
처음엔 아래와 같이 완탐 백트래킹으로 풀어서 틀렸다.
답은 맞았지만, 시간초과가 나와 틀렸다.

나름 시간복잡도에서 2초 텀이라 가능할거라고 생각했는데,
어림도 없었던 모양이다.
아쉽다.

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
    static int max = 0;
    static boolean[] visited;
    static List<Character> alpha;
    static String[] arr;
    static int[] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        arr = new String[N];
        visited = new boolean[26];
        nums = new int[10];

        for(int i = 0 ; i < N ; i++) {
            arr[i] = br.readLine();
        }

        String s1 = "";
        for(String s2 : arr) {
            s1 += s2;
        }

        char[] c1 = s1.toCharArray();
        ArrayList<Character> c2 = new ArrayList<>();

        for(char c : c1) {
            c2.add(c);
        }

        alpha = c2.stream().distinct().collect(Collectors.toList());

        backTracking(0);

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();


    }
    static void backTracking(int depth) {
        if(depth == alpha.size()) {
            max = Math.max(max, makeSum());
            return;
        }

        for(int i = 0 ; i < 10 ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            nums[alpha.get(depth) - 'A'] = i;
            backTracking(depth+1);
            visited[i] = false;
        }
    }


    static int makeInteger(String s) { //String형태를 숫자로 (ex : AAA -> 222)
        String answer = "";
        char[] arr = s.toCharArray();

        for(char c : arr) {
            answer += nums[c - 'A'];
        }

        return Integer.parseInt(answer);
    }

    static int makeSum() { // 주어진 String들을 순회하며 합 구하기
        int sum = 0;

        for(String s : arr) {
            sum += makeInteger(s);
        }

        return sum;
    }



}