[백준 1039] 단어 수학 - JAVA

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 $N$개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 $0$부터 $9$까지의 숫자 중 하나로 바꿔서 $N$개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때,
A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면,
두 수의 합은 $99437$이 되어서 최대가 될 것이다.

$N$개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 $N(1 ≤ N ≤ 10)$이 주어진다. 둘째 줄부터 $N$개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 $10$개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

---

접근 방법

단순히 생각해봤을 때 다음과 같은 기준으로 알파벳을 숫자로 바꿔야 합니다.

• 자릿수가 가장 높게 존재하는 알파벳을 가장 높은 숫자로 변경
• 자릿수가 높은 숫자가 여러개라면 그 중 더 많은 개수가 존재하는 알파벳을 높은 숫자로 변경
• 가장 높은 자릿수 또한 동일하다면 다음 자릿수에서 알파벳의 수를 비교

결국 이 문제는 더 높은 자릿수에 알파벳이 더 많은 순서대로 숫자를 선정해주면 됩니다.

그러면 이 문제를 어떻게 풀 수가 있냐 하면 각 자릿수마다 가중치를 주는 것입니다.

• 첫 번째 자릿수의 특정 알파벳은 $1$의 가중치
• 두 번째 자릿수의 특정 알파벳은 $10$의 가중치
• $N$ 번째 자릿수의 특정 알파벳은 $10^N$의 가중치

그러면 이 가중치를 어떻게 저장하느냐 하면
$A\ to\ Z$까지 어떤 알파벳들이 나왔으며 가중치가 가장 높은 알파벳을 선정해야되므로
weight[AtoZ] = weight[26] 으로 배열을 선언해주면 각 인덱스는 알파벳을 의미하게 됩니다.

입력된 문자열들을 $for$문을 사용해서 각 문자의 위치에 따라 가중치를 부여하고
계산된 가중치를 weight배열에 누적시킵니다.

마지막으로 이 가중치가 가장 높은 알파벳부터 순차적으로 숫자로 변환해야되기 때문에
PriorityQueue를 사용해서 하나씩 꺼내주면서
숫자를 부여했습니다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] weights = new int[26];

        for (int i = 0; i < N; i++) {
            char[] spells = br.readLine().toCharArray();
            int L = spells.length;

            for (int j = 0; j < L; j++) {
                char c = spells[j];
                int digit = L - j - 1;

                weights[c - 65] += (int) Math.pow(10, digit);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < 26; i++) {
            if (weights[i] != 0) pq.offer(weights[i]);
        }

        int answer = 0;
        int mul = 9;

        while(!pq.isEmpty()) {
            int weight = pq.poll();
            answer += weight * mul;
            mul--;
        }

        System.out.println(answer);
    }
}