[백준] 1036번. 36진수(JAVA)

문제

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

---

풀이(19분)

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

public class Main {

	static List<String> inputs = new ArrayList<>();
	static final int MAX_LEN = 60;

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

		int N = Integer.parseInt(br.readLine());
		Map<Character, int[]> maps = new HashMap<>();

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			inputs.add(s);
			for (int j = s.length() - 1; j >= 0; j--) {
				char cur = s.charAt(j);
				maps.putIfAbsent(cur, new int[MAX_LEN]);
				int idx = s.length() - 1 - j;
				maps.get(cur)[idx] += 1;
			}
		}

		// Z 치환 시 이득 계산
		PriorityQueue<Node> pq = new PriorityQueue<>();

		for (int i = 0; i < 36; i++) {
			char c = toChar(i);
			maps.putIfAbsent(c, new int[MAX_LEN]);

			long[] gain = new long[MAX_LEN];
			int[] arr = maps.get(c);

			long diff = 35 - i; // Z - 원래 문자 값
			long carry = 0;

			for (int j = 0; j < MAX_LEN; j++) {
				long v = (long) arr[j] * diff + carry;
				gain[j] = v % 36;
				carry = v / 36;
			}

			pq.add(new Node(i, gain));
		}

		// K개 문자 선택
		int K = Integer.parseInt(br.readLine());
		Set<Character> set = new HashSet<>();
		for (int i = 0; i < K; i++) {
			Node cur = pq.poll();
			set.add(toChar(cur.idx));
		}

		// 최종 합 계산
		long[] result = new long[MAX_LEN];

		for (String s : inputs) {
			long carry = 0;
			for (int i = s.length() - 1; i >= 0; i--) {
				char c = s.charAt(i);
				int val = toNumber(c);
				if (set.contains(c)) val = 35; // Z로 치환

				int idx = s.length() - 1 - i;
				long sum = result[idx] + val + carry;
				result[idx] = sum % 36;
				carry = sum / 36;
			}

			// 자리 올림
			int pos = s.length();
			while (carry > 0) {
				long sum = result[pos] + carry;
				result[pos] = sum % 36;
				carry = sum / 36;
				pos++;
			}
		}

		// 출력 (뒤에서부터)
		StringBuilder sb = new StringBuilder();
		int start = MAX_LEN - 1;

		while (start > 0 && result[start] == 0) start--;
		for (int i = start; i >= 0; i--) {
			sb.append(toChar((int) result[i]));
		}

		System.out.println(sb);
	}

	static class Node implements Comparable<Node> {
		int idx;
		long[] gain;

		public Node(int idx, long[] gain) {
			this.idx = idx;
			this.gain = gain;
		}

		@Override
		public int compareTo(Node o) {
			for (int i = MAX_LEN - 1; i >= 0; i--) {
				if (this.gain[i] != o.gain[i]) {
					return Long.compare(o.gain[i], this.gain[i]); // 큰 이득 우선
				}
			}
			return 0;
		}
	}

	static int toNumber(char c) {
		if (Character.isDigit(c)) return c - '0';
		return c - 'A' + 10;
	}

	static char toChar(int num) {
		if (num >= 0 && num <= 9) return (char) ('0' + num);
		return (char) ('A' + (num - 10));
	}
}

---

문제 풀이 전략

 

1. 각 문자의 자리수 기여도를 저장한다.

문자 하나는 여러 문자열의 여러 자리에서 등장할 수 있으므로,
각 문자에 대해 0~50번째 자리까지의 기여도를 저장할 배열을 만든다.

• 문자별로 int[51] 배열을 두고
• 자리수마다 등장 횟수를 누적하여 기록한다.

 

2. 한 자리에서의 기여도가 35를 초과하면 올림(carry)을 수행한다.

36진수는 한 자리의 최대값이 35이므로,
문자 × 등장 횟수의 값이 35를 초과하면 다음 자리로 올려야 한다.

즉,
해당 자리의 값을 감소시키고
다음 자리의 값을 증가시키는 방식으로 올림 처리를 반복한다.

 

3. 문자를 Z로 바꿨을 때의 증가량을 계산한다.

각 문자를 ‘Z(=35)’로 변경하면,
해당 문자가 원래 가진 값과 35의 차이만큼
각 자리에서의 기여도가 증가한다.

따라서
자리수에 따른 증가량을 모두 계산하여 가치(value)를 구한다.

 

4. 증가 가치가 큰 문자 K개를 선택한다.

모든 문자에 대해 변화할 가치가 계산되면,
그 중 증가량이 가장 큰 문자 K개를 선택한다.

우선순위 큐나 정렬을 사용해
가장 큰 가치 K개를 효율적으로 뽑아낼 수 있다.

 

5. 선택된 문자를 Z로 변환하고 최종 값을 계산한다.

선택된 문자 K개는 모두 Z로 처리하고,
갱신된 자리수 기여도 배열을 기반으로
최종 36진수 값을 계산하고 출력한다.