Site avatar

☀️ Log

개발과 학습에 대한 생각을 기록하는 공간입니다.

GitHub

1036. 36진수

4 min read

INFO

1. 문제 이해

핵심 요구사항

  • 36진법 숫자 N개에서 K개의 숫자를 고름 → 전체에서 그 숫자를 Z로 변경 → 다 더함
  • 목적: 최댓값을 구하는 프로그램

제한 조건

  • 변수 범위
    • N ⇐ 50
    • 수의 길이 ⇐ 50
    • 0 ⇐ K ⇐ 36
  • 시간: 2초
  • 메모리: 128MB

BigInteger 타입 사용

  • 문제에서 주어지는 36진수의 수는 최대 50자리 ⇒
  • Long 자료형이 감당할 수 있는 수의 범위는 으로 택도 없이 부족함
  • 따라서 BigInteger 타입을 사용해야함.

2. 사고의 흐름 (Thinking)

  • ❌ 제외: 완전 탐색 (Brute Force)

    • 완전탐색에서 최악의 경우: K=18
      • 36개의 숫자 중에서 18개를 고르는 경우의 수만 9,075,135,300번… 절대 안됨

  • ❌ 1차 시도: 그리디 (Greedy)

    • 50개 중에서 높은 자리의 숫자부터 고르거나
    • 더 많이 등장하는 숫자부터 고르거나
    • 동일한 경우 더 작은 숫자
    • Z로 바꿨을 때 영향이 더 큰 수부터 K개 골라서 Z로 바꾸기

  • ✏️ 2차 시도: 그리디 (Greedy)

    • “Z로 바꿨을 때 영향이 더 큰 수부터 K개 골라서 Z로 바꾸기” 라는 방향성은 동일
    • 단, 1차 시도에서 알 수 있다시피 간단하게 판단하기에는 기준이 많음
    • 따라서 어떤 숫자가 가장 Z로 바뀌었을 때 가장 영향이 큰 지를 직접 구하는 방향을 채택
      • 주어진 수의 각 숫자에 대해서 (Z-해당 숫자) * 자릿수를 구하고, 각 숫자 별로 누적해 더함.
      • 모든 수를 다 연산한 후, 더한 수 중 가장 큰 수 K개를 원래 수에 더 함.

3. 풀이 및 코드 (Solution)

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, K;
        BigInteger original = BigInteger.ZERO, result = BigInteger.ZERO;
        String[] nums;
 
        BigInteger[] weights = new BigInteger[36];
        for (int i = 0; i<36; i++) {
            weights[i] = BigInteger.ZERO;
        }
 
        N = Integer.parseInt(br.readLine());
 
        nums = new String[N];
        for (int n=0; n<N; n++) {
            nums[n] = br.readLine();
            String num36 = nums[n];
            BigInteger offset = BigInteger.ONE;
            for (int i=num36.length()-1; i>=0; i--) {
                char c36 = num36.charAt(i);
                int c10 = convertTo10(c36);
 
                original = original.add(BigInteger.valueOf(c10).multiply(offset));
                weights[c10] = weights[c10].add(BigInteger.valueOf(35 - c10).multiply(offset));
 
                offset = offset.multiply(BigInteger.valueOf(36));
            }
        }
        K = Integer.parseInt(br.readLine());
 
        Arrays.sort(weights, Collections.reverseOrder());
 
        for (int i=0; i<K; i++) {
            original = original.add(weights[i]);
        }
        System.out.println(original.toString(36).toUpperCase());
 
    }
 
    static int convertTo10(char c) {
        if (c >= 65) return c-'A' + 10;
        else return c-'0';
    }
 
}
  • 시간 복잡도:
    • 수의 모든 자릿수를 다 돌기 때문에 주어지는 (수의 개수 수의 길이)이다.
    • 동시에 BigInteger의 덧셈/곱셈은 자릿수에 비례하기 때문에 수의 길이를 다시 한번 곱해서 이 된다.

4. 회고 (Retrospective)

  • BigInteger 처음 써본다. 이런게 있는지도 처음 알았다. 더 익숙해져야지
  • 그리디라고 어어어엄청 그리디하게 풀지는 않는 경우가 있다. 이 문제의 경우에도 변화값을 다 구하고 그중에서 최댓값을 구하는 방식이다.

Computer PS