백준 1036번 : 36진수 자바
🧫 문제 분석
✔️ 출처
📖 문제
주어진 입력 중 Z로 k개 만큼 바꾸고 모두 더한 값이 최댓값이 되게 구하고, 그 값을 36진수로 변환하여 출력
정말정말 많은 시간을 썼고, 다른 블로그의 앞부분만 슬쩍봐서 큰 수를 어떻게 다루는지 참고하면서 풀었다.
결국에는 내가 생각한 아이디어와 로직이 맞았고, 큰 수를 다루는 BigInteger를 잘 안써서 떠오르지 못했던 것이다..
나의 경우
0~9 는 배열 각 인덱스 0~9에 1:1로 사용
A~Z는 -'7'을 해주면 'A' - '7' = 10이 되므로
배열을 35까지 만든 후
배열의 인덱스 0~9 A~Z까지 0~35로 사용하였다.
이 문제에서 중요한 것은
Z로 바꾼 K개의 숫자가 무엇이냐다.
맨 앞자리 수를 Z로 만든다고 무조건 최댓값이 나오는 것이 아니다.
예를 들어 이런 예제가 있다고 치자
3
Y2
1
1
1
답 : 100여기서 Y의 자릿수가 제일 크기에 Y를 Z로 바꾸면 최댓값이 되지 않을까 싶지만
실제로 계산해보면 1을 Z로 만드는게 더 큰 값이 나온다.
참고로 Y를 Z로 변환시 Z6이 된다.
k개를 뽑을 때
변화 값이 가장 큰 수를 Z로 만들어야 하기에
(35 - 수) * 35^자릿수이렇게 해서 가장 큰 변화값을 가지는 수를 뽑아야한다.
int, long 형을 쓰면 안되는 이유는 문제에서 수의 길이가 50자리라고 했다.
35^50은 이미 범위를 넘어선다.
따라서 BigInteger을 사용하면 된다.
🔅 문제 풀이
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
HashMap<Integer, BigInteger> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
String[] word = new String[n];
int[] arr = new int[36];
int min = 100, max = 0;
for (int i = 0; i < n; i++) {
word[i] = br.readLine();
min = Math.min(word[i].length(), min);
max = Math.max(word[i].length(), max);
for (int j = 0; j < word[i].length(); j++) {
char number = word[i].charAt(j);
BigInteger bInt = new BigInteger("0");
// 최댓값을 구하기 위한 개수 구하기
int power = word[i].length() - j;
int key = number >= 'A' ? number - '7' : number - '0';
BigInteger value = map.getOrDefault(key, bInt);
bInt = BigInteger.valueOf(35);
bInt = bInt.pow(power).multiply(BigInteger.valueOf(35 - key)).add(value);
map.put(key, bInt);
}
}
// 변화 값이 가장 큰 수 대로 숫자를 오름차 정렬
List<Map.Entry<Integer, BigInteger>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
int k = Integer.parseInt(br.readLine());
if (k != 0) {
for (int i = 0; i < k; i++) {
if (list.size() <= i) break;
Map.Entry<Integer, BigInteger> entry = list.get(i);
arr[entry.getKey()] = 35;
}
}
int[] nums = new int[53];
calculateNum(word, arr, nums);
int idx = change36(nums);
// 36진수로 바꿔서 출력
for (int i = idx - 1; i >= 0; i--) {
char cc = (char) (nums[i] >= 10 ? (nums[i] + '7') : (nums[i] + '0'));
sb.append(cc);
}
bw.write(sb.toString().isEmpty() ? "0" : sb.toString());
bw.flush();
bw.close();
}
private static void calculateNum(String[] word, int[] arr, int[] nums) {
// 각 자리수의 값 계산
for (int i = 0; i < word.length; i++) {
for (int j = 0; j < word[i].length(); j++) {
char c = word[i].charAt(word[i].length() - j - 1);
if (arr[getIndex(c)] != 0) nums[j] += 35;
else nums[j] += getIndex(c);
}
}
}
// 36진수 계산
private static int change36(int[] nums) {
int idx = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > 0) {
if (nums[i] / 36 > 0) {
nums[i+1] += nums[i] / 36;
nums[i] %= 36;
}
idx = Math.max(idx, i+1); // 끝에 있는 수의 자릿수를 세기
}
}
return idx;
}
private static int getIndex(char c) {
return c >= 'A' ? c - '7' : c - '0';
}
}
36진수 계산 메서드에서
따로 idx 변수를 써서 36진수로 계산된 자릿수의 크기를 미리 카운팅 할 건데
왜 idx++ 이 아니라 Math.max() 를 썼느냐
아래의 예시를 보면 이해할 수 있다.
2
ZZZ000000000000ZZ
1
0
정답 : ZZZ00000000000100
오답 : 000100
기존의 자릿수에 값이 0이면 내가 짠 로직은 넘어가게 되있다.
따라서 Math.max 함수를 써서 마지막으로 뜬 가장 큰 자릿수의 수의 인덱스를 세기 위함이다.
물론 마지막 큰 숫자의 자릿수만 알면 되므로 아래와 같이 써도 된다.
// 36진수 계산
private static int change36(int[] nums) {
int idx = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > 0) {
if (nums[i] / 36 > 0) {
nums[i+1] += nums[i] / 36;
nums[i] %= 36;
}
// idx = Math.max(idx, i+1);
idx = i;
}
}
return idx + 1;
}
❗ 오답노트 / 필요한 지식
- 어려웠다. 어떻게 푸는지는 알겠는데 k개를 뽑을때 예외사항, 큰 수의 처리, Map의 정렬 이런 것 때문에 더 막힌듯 하다.