단어 수학

https://www.acmicpc.net/problem/1339

풀이

만약 AAA가 들어왔다면 A가 111개가 있다고 생각을 하여 우선 순위 큐에 빈도수가 높은 순으로 정렬 후 하나씩 꺼내 높은 숫자를 우선 배정해주는 식으로 풀이했다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {
    static int n, m, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        String[] alpha = new String[10];

        HashMap<String, Integer> pairs = new HashMap<>();
        String[] def = new String[n];

        for (int i = 0; i < n; i++) {
            def[i] = br.readLine();
            String[] line = def[i].split("");
            int k = line.length - 1;
            for (String s : line) {
                if (pairs.containsKey(s)) {
                    int num = pairs.get(s);
                    num = num + (int) Math.pow(10, k);
                    pairs.put(s, num);
                } else {
                    pairs.put(s, (int) Math.pow(10, k));
                }
                k--;
            }
        }

        PriorityQueue<Pair> priorityQueue = new PriorityQueue<>();
        pairs.forEach((key, value) -> priorityQueue.offer(new Pair(key, value)));

        int idx = 9;
        while(!priorityQueue.isEmpty()) {
            Pair p = priorityQueue.poll();
            alpha[idx] = p.c;
            idx--;
        }

        for(int i = 0;i<10;i++) {
            for(int j = 0;j<n;j++) {
                if (alpha[i] != null) {
                    def[j] = def[j].replaceAll(alpha[i], Integer.toString(i));
                }
            }
        }

        long ans = 0;
        for(int i = 0;i<n;i++) {
            ans = ans + Long.parseLong(def[i]);
        }

        bw.write(ans+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Pair implements Comparable<Pair> {
    public String c;
    public int freq;

    public Pair(String c, int d) {
        this.c = c;
        this.freq = d;
    }

    @Override
    public int compareTo(Pair o) {
        return -1 * Integer.compare(this.freq, o.freq);
    }
}