백준 1036 자바 - 36진수 (BOJ 1036 JAVA)

[ 백준 1036 - 36진수 ]

[ 코드 보기 (깃헙 링크) ]

 

  

  23046(큰 수 뒤집기)를 얼마전에 푼 이후로 당분간 큰 수 연산 관련된건 안보려 했으나, 그냥 그리디에 36진수 자리수 올림 (carry) 정도만 필요한것같아 시도했다가 로직 자체가 틀리면서 물렸다.. 그 뒤로 맞는 것 같은 로직을 세웠는데, 결국 더 많은 큰 수 연산이 필요했다 ㅠㅠ 그래도 이번엔 BigInteger로도 입력 숫자 자체가 적다보니 문제없어서 다행이었다.. 로직 자체는 그리디인데, 로직보다도 구현 자체가 빡쌨던 문제이다.

 

 

[ 틀린 로직 ]

  가끔씩 틀린 로직도 적는데, 누구 보라고 적는건 아니고 나중에 내가 다시 봤을 때 이렇게 틀렸었지! 하기 위해서이다.  그러니 아래쪽의 'AC 코드 해설'로 바로 넘어가도 상관없음.

  처음엔 단순히 더 높은 자리수에 'Z'가 많을수록 좋을꺼라 생각했다. 따라서 아래와 같은 표를 일단 확인했다.

  세로로는 위아래로 0,1,2,... ,A,B,C,D,.... Z 까지고, 가로로는 뒤에서부터 몇번째 자리수인지를 나타낸다.

그럼 저렇게 표만 만들어두고, 가장 큰 자리수부터 가장 많은 카운팅갯수 + 0에 가까울수록 가중치를 둬서 k개를 고르면 될줄 알았다!

 

  그렇게 짠 코드가 아래와 같다.

[ 틀린 코드임 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private int nextInt() throws Exception      { return Integer.parseInt(br.readLine()); }
    private String nextLine() throws Exception  { return br.readLine(); }
    private StringBuilder sb = new StringBuilder();
    private void write(Object o) { sb.append(o); }
    private void flush() { System.out.println(sb); }

    private int atoi(char c) {
        if (c <= '9') return c-'0';
        return c-'A'+10;
    }

    private char itoa(int i) {
        if (i <= 9) return (char)('0'+i);
        return (char)('A'+i-10);
    }

    private boolean[] choice(int maxDigit, int[] maxCnt, int[][] cnt, int k) {
        boolean[] v = new boolean[35+1];
        v[35] = true;   //except 'Z'. 'Z' is already 'Z'!
        if (k == 0) return v;

        int selectedCnt = 0;

        for (int digit = maxDigit; digit >= 1; digit--) {
            int digitMaxCnt = maxCnt[digit];
            if (digitMaxCnt == 0) continue;

            for (int targetCnt = digitMaxCnt; targetCnt >= 1; targetCnt--) {
                for (int i = 0; i <= 35; i++) {
                    if (v[i] || cnt[i][digit] != targetCnt) continue;
                    v[i] = true;
                    if (++selectedCnt == k)
                        return v;
                }
            }
        }

        return v;
    }

    private void solution() throws Exception {
        int n = nextInt();

        int[][] cnt = new int[35+1][50+1];
        char[][] arr = new char[n][];
        int[] maxCnt = new int[50+1];
        int maxDigit = 0;

        for (int i = 0; i < n; i++) {
            String cur = nextLine();
            if (cur.length() > maxDigit)
                maxDigit = cur.length();
            arr[i] = cur.toCharArray();

            for (int j = 0; j < cur.length(); j++) {
                int num = atoi(cur.charAt(j));
                cnt[num][cur.length()-j]++;
                maxCnt[cur.length()-j] = Math.max(maxCnt[cur.length()-j], cnt[num][cur.length()-j]);
            }
        }

        int k = nextInt();
        boolean[] selectedNum = choice(maxDigit, maxCnt, cnt, k);
        long[] answer = new long[maxDigit+1+1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                int digit = arr[i].length - j;
                int cur = atoi(arr[i][j]);
                answer[digit] += (selectedNum[cur] ? 35 : cur);
            }
        }

        for (int digit = 1; digit <= maxDigit; digit++) {
            long cur = answer[digit];
            answer[digit] = cur % 36;
            answer[digit+1] += cur / 36;
        }

        boolean firstZeroChk = true;
        for (int digit = maxDigit+1; digit >= 1 ; digit--) {
            if (firstZeroChk && answer[digit] == 0) continue;
            firstZeroChk = false;
            write(itoa((int)answer[digit]));
        }

        flush();
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

근데 계속 틀려서 생각해보니, 다음과 같은 경우 틀린다.

 

29
Y00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
1

이 경우 위 로직으로는 가장 자리수가 큰 'Y'를 변경하게 된다. 실제론 그보다 '0'을 'Z'로 변경하는게 이득이다.

 

 

[ AC 코드 해설 ]

[ 코드 보기 (깃헙 링크) ]

 

  그럼 결국 '틀린 로직'을 해결하려면, 자리수와 관계없이 36진수의 각 수 (0,1,2,3,...,Z)를 실제로 바꿔봐서 이 중 뭐가 이득인지 봐야 한다. 그렇다고 물론 모든 수를 전부 바꿔보고 brute force 돌리기엔 문제가 있다.

 

36진수로 바로 생각해보긴 어려우니 10진수로 생각해보자.

 

1234

 324

 567

 

이렇게 있다면, 각 수가 나온 자리수와 몇 번 나왔는지를 판단해 아래와 같이 카운팅을 해볼 수 있다. (해당 숫자가 나올 때 마다 '10^(우측부터 자리수 인덱스)' 를 더해줌

1 : 1000

2 : 110

3 : 110

4 : 2

5 : 100

6 : 10

7 : 1

 

그리고 10진수이니 'Z'가 아니라 k개를 '9'로 변경한다고 해보자. 그럼 위의 전처리된 형태에서 각 숫자를 '9'로 변경했을 때 전체 값에 얼마나 영향을 끼치는지 알 수 있다. 해당 값은 '위의 카운팅 결과 * (9 - 해당 숫자)' 로 가능하다.

 

1 : 1000 * (9-1) = 8000

2 : 770

3 : 660

4 : 10

5 : 400

6 : 30

7 : 2

 

그럼 이걸 기준으로 정렬한다.

1:8000 > 2:770 > 3:660 > 5:400 > 6:30 > 4:10 > 7:2

 

그럼 이제 좌측부터 k개를 9로 변경해주면 답이 된다. (k가 2라면 1과 2를 9로 변경, k가 4라면 1,2,3,5를 9로 변경)

 

---

 

그럼 위의 로직을 36진수로 변경하면 된다.

카운팅은 36^(우측부터 해당 수가 나온 인덱스)

'Z'로 변경 시 얼마나 영향을 끼칠지는 '카운팅 결과 * ('Z=35' - 해당 숫자)'가 된다.

 

그럼 입력이

ABCD

BCD

AAA

C

 

였다면 다음과 같이 계산된다. (카운팅값에 해당하는 코드가 85line 까지이다 / 'Z'로 변경시 영향 수치에 해당하는 코드가 87~88 line이다.)

이걸 'Z'로 변경시 영향 수치에 따라 정렬한 후, 이제 k개를 'Z'로 변경하면 된다. (코드의 92~96 line)

만약 k = 2 였다면 위의 입력은 아래와 같이 변경된다.

 

ZZCD

ZCD

ZZZ

C

 

그리고 실제 입력되었던 문자열을 치환해서 36진수로 더해준다. (코드의 98~105 line)

그 후 낮은 자리수부터 높은 자리수로 올라가며 carry를 올려준다. (코드의 107~111 line)

 

최종적으로 출력해주면 된다.

참고로, 위에서는 카운팅값 및 'Z'로 변경시 영향 수치를 10진수로 변경해서 표현했었다. 이는 36진수 체계에 해당하는 클래스를 새로 만들지 않고 처리하기 위해 그랬다. 그리고 최대 36^50-1까지의 엄청난 수가 나올 수 있으므로 BigInteger를 썼는데, 좀 더 하드난이도로 하려면 BigInteger로 하지 않고 36진수 체계에 해당하는 클래스를 직접 만들어서 하면 된다. (51칸짜리 int형 배열로 표현 가능하지만, 배열끼리의 36진수 곱셈과 덧셈을 구현해야 함)

 

혹은 파이썬 쓰면 쉽다. 실제로 이 문제의 경우 백준 '난이도 기여' 코맨트를 보니 포기하고 파이썬 써서 해결한 사람이 꽤 있는것같다 ㅋㅋㅋ