[백준 1339] 단어 수학

문제 링크 : https://www.acmicpc.net/problem/1339

이 문제는 그리디 알고리즘을 이용하여 풀 수 있습니다. 가장 처음 이 문제를 풀 때 HashMap에 각 알파벳 별 최대의 자릿수를 저장한 후 이 순서대로 9부터 숫자를 배치하는 방식을 생각했습니다. 하지만 이 경우는 한 가지 크게 간과한 점이 있습니다. 바로 최대의 자릿수가 작더라도 해당 자릿수에 많이 존재하거나 해당 알파벳의 총합이 최대의 자릿수의 알파벳보다 클 수 있다는 점입니다. 합을 고려하지 않고 단순히 인덱스만을 고려하여 문제의 정답을 맞추지 못했습니다.

따라서 합을 고려하여 코드를 짭니다. 알파벳 int 배열을 생성한 후 각 인덱스에 알파벳 별 자릿수를 계속 더해줍니다. 이후 이 값을 내림차순 정렬하여 큰 인덱스에 해당하는 알파벳에 높은 숫자를 할당하는 방식으로 문제를 풀었습니다.

다음은 코드입니다.

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

class Main{
    static int N;
    static int[] alphabet = new int[26];
    static PriorityQueue<Word> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<str.length();j++){
                int exp = str.length() - (j+1);
                int idx = str.charAt(j) - 'A';
                alphabet[idx] += Math.pow(10,exp);
            }
        }

        for(int i=0;i<alphabet.length;i++) queue.add(new Word(i,alphabet[i]));

        int sum = 0;
        int num = 9;
        while(!queue.isEmpty()){
            Word curr = queue.poll();
            sum += curr.val*num;
            num--;
        }
        System.out.println(sum);
    }

    static class Word implements Comparable<Word>{
        int idx;
        int val;

        Word(int idx, int val){
            this.idx = idx;
            this.val = val;
        }

        @Override
        public int compareTo(Word o) {
            return o.val - this.val;
        }
    }
}