백준 1036 36진수

문제

---

1036번: 36진수 (acmicpc.net)

해결방법

---

• 최대값을 구하는 방법 각 자리수의 수마다 해당 수를 Z로 치환했을 때의 값과 차를 더해서 각각 36개의 배열에 저장한다. 예를 들어 12가 있을 때 2에 해당하는 배열에 1Z - 12의 값을 더해주고 1에 해당하는 배열에 Z2 - 12 값을 모두 더해준다. 모든 수를 더한 값에 배열에 들어있는 가장 큰 수 k 개를 뽑아 다 더해준다.
  
• 36진수 구현 클래스로 36진수를 구현하였다. 각 자리수 계산에 사용하기 위해 36진수를 10진수로 바꾸는 함수와 10진수를 36진수로 바꾸는 함수를 작성했다. 36진수 클래스는 36진수 문자열을 받아와서 거꾸로 저장해놓고 순서대로 더하도록 했다.
  

동작과정

---

1. 모든 숫자를 더할 36진수 객체 sum과 각 숫자별 합을 구할 36진수 객체 36개가 있는 배열을 준비한다.
2. 배열의 초기 값은 모두 0으로 설정한다.
3. 문자열을 입력 받으면서 sum에 모두 더해주고 문자열을 돌면서 해당 자리의 숫자를 Z로 치환한 차이 값을 해당 숫자 배열에 더해준다.
4. 배열의 내용을 모두 pq에 담고 그중 k개 만큼을 뽑아 sum에 더해준다.

코드

---

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {

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

        int N = Integer.parseInt(in.readLine());

        // 0~Z 까지의 숫자별로 Z로 치환 시 원래 숫자와의 차이를 다 더해주기 위한 배열
        Decimal[] plus = new Decimal[36];

        // 모두 0으로 설정한다.
        for(int i = 0; i < 36; i++)
            plus[i] = new Decimal("0");

        // 주어진 숫자들을 모두 더하기 위한 36진수 객체
        Decimal sum = new Decimal("0");

        for(int i = 0; i < N; i++) {
            String s = in.readLine();
            sum.plus(new Decimal(s));

            // 문자열의 각 자리를 돌면서 해당 자리의 숫자를 Z로 치환한 값과의 차이를 해당 숫자의 배열에 추가한다.
            for(int j = 0; j < s.length(); j++) {
                int value = getValue(s.charAt(j));

                plus[value].plus(s.charAt(j), s.length()-1-j);
            }
        }

        int K = Integer.parseInt(in.readLine());

        // 0~Z 중 Z로 치환시 값이 가장 큰 숫자들을 K 만큼 뽑기 위한 우선순위 큐
        PriorityQueue<Decimal> pq = new PriorityQueue<>();
        pq.addAll(Arrays.asList(plus));

        // 가장 큰 값을 K개 뽑아서 sum에 더해준다.
        for(int i = 0; i < K; i++) {
            sum.plus(pq.poll());
        }

        out.write(sum.getDigit());
        out.flush();
    }

    // 36진수의 한 숫자를 10진수로 변환
    static int getValue(char value){
        if(Character.isDigit(value))
            return value - '0';
        else
            return 10 + value - 'A';
    }

    // 10진수를 36진수의 한 숫자로 변환
    static char toDecimal(int num) {
        if(num < 10)
            return (char)(num + '0');
        else
           return (char)(num - 10 + 'A');
    }

    // 36진수를 구현한 클래스
    static class Decimal implements Comparable<Decimal>{
        String digit;
        int length;

        // digit은 36진수 문자열, 편하게 더하기 위해 거꾸로 저장해놓음
        public Decimal(String digit) {
            StringBuilder sb = new StringBuilder();

            for(int i = digit.length()-1; i >= 0; i--)
                sb.append(digit.charAt(i));

            this.digit = sb.toString();
            this.length = digit.length();
        }

        // 다른 36진수 값을 현재 값에 더해줌
        public void plus(Decimal other) {

        	// 둘중 자리수가 큰 값 까지 더하기 위해 length 설정
            int length = Math.max(other.length, this.length);
            // 현재 값을 새로운 값으로 설정해주기 위한 StringBuilder
            StringBuilder sb;

            sb = new StringBuilder();
            // 올리는 숫자 before
            int before = 0;
            // 각각 자리수의 수를 10진수로 바꿔서 더하고 다시 36진수로 변환한다. 36을 넘는 값은 before에 저장하여 다음 자리 수에 더해준다.
            for(int i = 0; i < length; i++) {

                int o1 = 0;
                int o2 = 0;

                if(this.length > i) {
                    if (Character.isDigit(this.digit.charAt(i)))
                        o1 = this.digit.charAt(i) - '0';
                    else
                        o1 = 10 + this.digit.charAt(i) - 'A';
                }

                if(other.length > i) {
                    if (Character.isDigit(other.digit.charAt(i)))
                        o2 = other.digit.charAt(i) - '0';
                    else
                        o2 = 10 + other.digit.charAt(i) - 'A';
                }

                int sum = (o1 + o2 + before);
                sb.append(toDecimal(sum % 36));
                before = sum / 36;
            }

            // 모든 덧셈을 끝내고 마지막자리에서 올라온 수가 있으면 그 수를 맨 뒤에 추가한다.
            if(before != 0)
                sb.append(toDecimal(before));

            // 현재 digit을 갱신한다.
            this.digit = sb.toString();
            this.length = digit.length();
        }

        // index의 자리에 해당하는 c와 Z의 차이 만큼의 값을 더해주기 위한 함수
        public void plus(char c, int index) {
            StringBuilder sb = new StringBuilder();

            // Z와 해당 문자 c 와의 차이
            sb.append(toDecimal(35 - getValue(c)));

            // index 만큼 0을 채워줘서 숫자의 자리를 설정
            for(int i = 0; i < index; i++)
                sb.append("0");

            // 구한 값을 더해줌
            this.plus(new Decimal(sb.toString()));
        }

        // 편하게 더하기를 하기 위해 거꾸로 저장해놓은 String을 원래 상태로 내보내기 위함
        public String getDigit() {
            StringBuilder sb = new StringBuilder();
            // 0이 앞에 있으면 0을 추가하지 않기 위함
            boolean zeroCount = true;

            for(int i = digit.length()-1; i >= 0; i--) {

                if(digit.charAt(i) == '0' && zeroCount)
                    continue;

                if(digit.charAt(i) != '0')
                    zeroCount = false;

                sb.append(digit.charAt(i));
            }

            // digit이 0으로 이루어져있다면 0을 내보냄
            if(sb.length() == 0)
                sb.append('0');

            return sb.toString();
        }

        @Override
        public int compareTo(Decimal o) {
            String s1 = this.getDigit();
            String s2 = o.getDigit();

            if(s1.length() == s2.length()) {
                return s2.compareTo(s1);
            }
            return s2.length() - s1.length();
        }
    }
}