[백준 1036] 36진수 - JAVA

BOJ Link

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

 

풀이 과정

그리디 + 큰 수 연산 + 구현 문제이다.
정답률이 시사하듯이 어렵고 엣지케이스도 많은 문제였다.

 

1. 다루는 수의 범위가 매우 크다. 때문에 이는 i번째 자리수를 i번째 인덱스로 치환하는 배열로 구현한다.

 

2. 조합으로 K를 구성하며 브루트포스할 경우, 최대 O(36!*50*50)이다. 그리디하게 접근해야한다.

어떤 알파벳을 Z로 바꿨을 때의 기대 값을 저장하여 기대 값이 가장 높은 K개의 알파벳을 구성한다.

 

3. 모든 문자열을 탐색하며 선택한 K개의 알파벳들을 Z로 치환한 후, 36진수로 변환하여 출력한다.

 

또한, 답을 도출할 땐 문자열의 앞이 36이상일 경우를 고려해야 하지만, 기대 값이 높은 알파벳을 K개 구성하는 경우는 하지 않아도 된다. 대소 비교만 수행하기 때문이다.

 

헤맨 부분

1. 36진수 이기 때문에, 가장 앞자리수인 i가 가장 큰 경우가 최적이라고 착각할 수 있다.

ex) 2진수에서, 1111(2)의 경우 앞자리가 2^3=8이다. 이는 2^2+2^1+2^0을 구하더라도 7이므로(7<8), 항상 앞자리가 큰 것이 최적이다.

그러나, 문자열이 50개 있으므로 이는 성립하지 않는다.

 

2. 해당 문자열을 숫자로 다룰 수 없다.

36^0 + 36^1 + ... + 36^50의 수를 다뤄야 한다. 이는 parseLong()의 radix를 36으로 설정하여도 다룰 수 없으며,

BigDecimal 또한 불가능하다.

(문제 기여에 "특정 언어에서 쉬운" 타이틀이 자주 보인다. 파이썬처럼 큰 수를 다루기 용이한 언어는 이점이 있다.)

 

3. 문제에서 N은 최대 50이하지만, i번째 자리수가 가장 큰 수로만 구성된 경우, 35*50=1750이다.

이는 단순히 i+1번째 값을 36으로 나누어 저장하여도, i+2번째 값이 1이될 수 있다. 즉, N=52까지 고려해야 한다.

(1750/36=48.61이다. 이는 다음 자리에서 36진수로 표현 불가능하다.)

 

4. 입력으로 주어지는 문자열의 크기가 상이하다. 문자열을 한개씩 완전히 처리하는 방식이 아닌, 문자열을 번갈아가며 idx를 비교하는 코드를 작성하는 경우, OutOfBound 하지 않도록 처리 해야한다.

 

유의할 점

출력의 크기를 50으로 고정해선 안되며, 맨 앞자리가 36진수로 표현 불가능할 경우에 대한 고려를 해야한다.

 

또한, 0을 조심해야한다. 답을 구성하기 위해 0을 trim하는 코드를 구성할 경우, 출력이 0인 경우가 반례이며,

0을 공백으로 replace한다면 중간에 0이 들어가는 경우가 반례이다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Z = 35;
        int N = Integer.parseInt(br.readLine());

        String[] arr = new String[N];
        int IM = 0;
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
            IM = Math.max(arr[i].length(), IM);
        }

        int K = Integer.parseInt(br.readLine());
        int AM = 36;
        // 35*50=1750, 1750/36=48.6 즉, 같은 자리에 Z가 50개 입력될 경우, 다음 자리수로도 표현하지 못한다. 다다음 자리도 사용해야 한다.
        // 따라서 최대 N의 길이 50에 +2 한다.
        int NM = 50 + 2;

        int[][] comp = new int[AM][NM];
        Set<Integer> set = new HashSet<>();

        // 해당 알파벳을 Z로 바꿀 때 기대 값 저장 - 그리디하게 뽑기 위함
        for (int alpa = 0; alpa < AM; alpa++) {

            for (int idx = 0; idx < IM; idx++) {
                int total = 0;

                for (int n = 0; n < N; n++) {
                    // 탐색하려는 인덱스가 현재 문자열에서 탐색 가능하면 값 누적
                    if (idx < arr[n].length()) {
                        int val = charToInt(arr[n].charAt((arr[n].length() - 1) - idx));

                        // 탐색하려는 인덱스의 문자가 Z로 바꾸려는 문자면 변경
                        if (val == alpa) val = Z;
                        total += val;
                    }
                }

                // 36진수로 변환
                comp[alpa][idx] += total;
                comp[alpa][idx + 1] += comp[alpa][idx] / 36;
                comp[alpa][idx] %= 36;
            }
        }

        // 그리디하게 K만큼 알파벳을 뽑음
        for (int i = 0; i < K; i++) {
            getGreedyAlpa(set, comp, NM, AM);
        }

        // 뽑은 알파벳들을 Z로 replace
        for (int e : set) {
            for (int i = 0; i < N; i++) {
                arr[i] = arr[i].replaceAll(alpaToString(e), "Z");
            }
        }

        int[] ans = new int[NM];

        for (int idx = 0; idx < IM; idx++) {
            int total = 0;
            for (int n = 0; n < N; n++) {
                if (idx < arr[n].length()) {
                    int val = charToInt(arr[n].charAt((arr[n].length() - 1) - idx));
                    total += val;
                }
            }
            ans[idx] += total;
            ans[idx + 1] += ans[idx] / 36;
            ans[idx] %= 36;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            sb.append(alpaToString(ans[i]));
        }

        // 맨 앞자리 탐색
        int firstIdx = -1;
        for (int i = NM - 1; i >= 0; i--) {
            if (ans[i] != 0) {
                firstIdx = i;
                break;
            }
        }
        // 0인 경우
        if (firstIdx == -1) {
            System.out.println(0);
        } else {
            String ansS = sb.reverse().toString();

            // 맨 앞의 값이 36이상일 때 예외 처리
            int first = ans[firstIdx];

            System.out.println(first >= 36 ?
                    alpaToString(first / 36) + alpaToString(first % 36) + ansS.substring(sb.length() - 1 - firstIdx + 1)
                    : ansS.substring(sb.length() - 1 - firstIdx));
        }

    }

    public static int charToInt(char c) {
        if (c <= '9') return c - '0';
        else return c - 'A' + 10;
    }

    public static String alpaToString(int alpa) {
        if (alpa <= 9) return String.valueOf(alpa);
        else return String.valueOf((char) (alpa + 'A' - 10));
    }

    public static void getGreedyAlpa(Set<Integer> set, int[][] comp, int NM, int AM) {
        for (int n = NM - 1; n >= 0; n--) {
            int max = 0;
            int malpa = -1;

            for (int alpa = 0; alpa < AM; alpa++) {

                // 가장 앞자리 수를 찾아
                if (!set.contains(alpa) && comp[alpa][n] != 0) {
                    // 더 크다면 갱신
                    if (comp[alpa][n] > max) {
                        max = comp[alpa][n];
                        malpa = alpa;
                    }
                    // 같다면
                    else if (comp[alpa][n] == max) {

                        int col = n;
                        // 마지막까지 비교하며 기대 값이 더 큰 알파벳을 뽑는다.
                        while (col >= 0 && comp[alpa][col] == comp[malpa][col]) col--;

                        if (col != -1) {
                            if (comp[alpa][col] > comp[malpa][col]) {
                                malpa = alpa;
                            }
                        }
                    }
                }
            }

            if (max != 0) {
                set.add(malpa);
                return;
            }
        }
    }
}