BOJ 1036 36진수

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

문제

36진법의 숫자는 0부터 9까지의 수와 알파벳 A에서 Z로 나타낸다. A부터 Z까지 알파벳은 10부터 35에 차례대로 대응한다.

36진법의 수 N개가 주어진다. 36진법 숫자(0-9, A-Z) 중에서 K개의 숫자를 고른다. 그러고 나서 N개의 수 모두에서 나타난 그 숫자를 Z로 바꾼다. 그 이후에 N개의 수를 모두 더한다.

이때 가능한 합의 최댓값을 구하는 프로그램을 작성하시오. 합의 최댓값도 36진수로 출력한다.

---

입력

첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 문제의 정답을 출력한다.

---

예제 입력 1

5
GOOD
LUCK
AND
HAVE
FUN
7

예제 출력 1

31YUB

예제 입력 2

1
HELLO
2

예제 출력 2

ZZLLO

… 이하 예제 생략

---

코드

0 ~ Z까지 각 숫자마다 등장한 자리수에 맞게 값을 더해 저장하고 해당 숫자를 Z로 바꿨을 때 원래 수와 가장 크기 차이가 많이 나는 순으로 K개를 뽑아 Z로 바꿔서 모든 숫자들을 더한다.

예를 들면, 4361이란 수가 있을 때

• values[1] += 1
• values[6] += 10
• values[3] += 100
• values[4] += 1,000

와 같이 저장해주고, 각 숫자를 Z로 바꿨을 때, 원래 숫자와의 차이가 큰 수를 우선해서 K개의 수를 Z로 바꾸는 방식이다.

위의 경우에는, K가 1일 경우에 숫자 4를 Z로 바꾸는 게 가장 차이가 크기 때문에 4를 Z로 바꿔준다.

• 원래 수 = 1,000 * 4 = 4,000
• Z로 바꿨을 때의 수 = 1,000 * 35 = 35,000

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static class PosVal implements Comparable<PosVal> {
        int position;
        BigInteger value, gap;

        public PosVal(int position, BigInteger value) {
            this.position = position;
            this.value = value;
            this.gap = value.multiply(new BigInteger(String.valueOf(35 - position)));
        }

        @Override
        public int compareTo(PosVal o) {
            return o.gap.compareTo(this.gap);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger[] values = new BigInteger[36];
        Arrays.fill(values, new BigInteger("0"));
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < input.length; j++) {
                char check = input[j];
                int targetIdx = check < 'A' ? check - '0' : 10 + check - 'A';
                values[targetIdx] = values[targetIdx].add(new BigInteger("36").pow(input.length - j - 1));
            }
        }
        int K = Integer.parseInt(br.readLine());
        PriorityQueue<PosVal> queue = new PriorityQueue<>();
        for (int i = 0; i < values.length; i++) {
            if(values[i].compareTo(new BigInteger("0")) > 0)
                queue.offer(new PosVal(i, values[i]));
        }

        BigInteger answer = new BigInteger("0");
        for (int i = 0; i < K && !queue.isEmpty(); i++) {
            PosVal check = queue.poll();
            answer = answer.add(check.value.multiply(new BigInteger("35")));
        }
        while (!queue.isEmpty()) {
            PosVal check = queue.poll();
            answer = answer.add(check.value.multiply(new BigInteger(String.valueOf(check.position))));
        }

        StringBuilder sb = new StringBuilder();
        while (answer.compareTo(new BigInteger("0")) > 0) {
            int mod = answer.mod(new BigInteger("36")).intValue();
            sb.insert(0,  (char) (mod > 9 ? 'A' + mod - 10 : '0' + mod));
            answer = answer.divide(new BigInteger("36"));
        }
        if(sb.length() == 0) sb.append('0');
        System.out.println(sb);
    }
}