[백준] 1036 36진수

1. 문제

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

1036번: 36진수

2. 접근방법

10진수로 바꾸어서 풀이하면 조금더 쉬웠을테지만

36^52을 담을 변수가 있는지 몰랐다. ( python이나 java BigInteger를 쓰면 담을 수 있다고 한다 )

 

나는 몰랐으니 어쩔 수 없이 36진수의 덧셈과 뺄셈을 구현해서 풀이했다.

 

아이디어 자체는 간단하다.

1. 주어진 모든 36진수들의 각 자릿수에 대해서 Z로 바꿨을 때 얼만큼 값이 커지는지 구해 숫자 별로 더해서 저장해둔다.

2. 동시에 주어진 모든 수의 합을 구해둔다.

3. 1. 에서 구한 배열을 정렬 시킨다.

4. 가장 큰 값부터 K개의 값을 2.에서 구한 합과 더 한다. (어떤 수를 바꿨는지는 중요하지 않다.)

5. 출력

 

3. 자바 코드

package backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class P1036_36진수 {
    static String diffDist[] = new String[36];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String totalSum = "0";
        for (int i = 0; i < 36; i++) diffDist[i] = "0";
        for (int i = 0; i < N; i++) {
            String oneLine = br.readLine();
            insConvertZDiff(oneLine);
            totalSum = plus(totalSum, oneLine);
        }
        Arrays.sort(diffDist, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return compareThirtySix(o1, o2);
            }
        });
        int K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            totalSum = plus(totalSum, diffDist[i]);
        }
        System.out.println(totalSum);
    }

    public static void insConvertZDiff(String a) {
        int aIdx = a.length() - 1;
        for (int i = 0; aIdx >= 0; aIdx--, i++) {
            String Z = "Z";
            String target = a.charAt(aIdx) + "";
            String diff = minus(Z, target);
            if (!diff.equals("0"))
                for (int j = 0; j < i; j++) diff = diff + "0";
            int targetInt = getTen(a.charAt(aIdx));
            diffDist[targetInt] = plus(diffDist[targetInt], diff);
        }
    }

    public static int compareThirtySix(String a, String b) {
        if (a.length() > b.length()) return -1;
        if (a.length() < b.length()) return 1;
        return b.compareTo(a);
    }

    public static String plus(String a, String b) {
        StringBuilder result = new StringBuilder();
        int aIdx = a.length() - 1;
        int bIdx = b.length() - 1;
        int upCount = 0;
        while (aIdx > -1 || bIdx > -1) {
            char aVal = aIdx < 0 ? '0' : a.charAt(aIdx);
            char bVal = bIdx < 0 ? '0' : b.charAt(bIdx);
            int aTen = getTen(aVal);
            int bTen = getTen(bVal);
            int value = aTen + bTen + upCount;
            if (value > 35) {
                upCount = 1;
                value = value - 36;
            } else {
                upCount = 0;
            }
            result.append(getThirtysix(value));
            aIdx--;
            bIdx--;
        }
        if (upCount == 1) result.append(1);
        return result.reverse().toString();
    }

    public static String minus(String a, String b) {
        StringBuilder result = new StringBuilder();
        int aIdx = a.length() - 1;
        int bIdx = b.length() - 1;
        int downCount = 0;
        while (aIdx > -1 && bIdx > -1) {
            char aVal = aIdx < 0 ? '0' : a.charAt(aIdx);
            char bVal = bIdx < 0 ? '0' : b.charAt(bIdx);
            int aTen = getTen(aVal) - downCount;
            int bTen = getTen(bVal);
            if (aTen < bTen) {
                downCount = 1;
                aTen = aTen + 36;
            } else {
                downCount = 0;
            }
            int value = aTen - bTen;
            result.append(getThirtysix(value));
            aIdx--;
            bIdx--;
        }
        return result.reverse().toString();
    }

    public static char getThirtysix(int num) {
        if (num < 10)
            return (char) ('0' + num);
        else
            return (char) ('A' + (num - 10));
    }

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

4. 마치며

디버깅이 너무 지옥이었따..