[백준, Java] 1036번, 36진수(그리디)

문제 링크

1036번: 36진수

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 0 ~ 9, A ~ Z으로 표현되는 36진수가 존재합니다.

2. 36진수 중 K개를 선택해서 'Z'으로 N개의 문자열을 변경합니다.

3. 이 때 가능한 최대값을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 알파벳에 대해서 'Z'으로 변경할 때 증가하는 수를 통해 K개 알파벳을 'Z'으로 변경한 뒤 수를 계산합니다.

 

3. 계산을 통해 얻은 최대 36진수의 값을 결과로 출력합니다.

 

 

'Z'으로 변경하기(그리디)

 

0 → Z으로 변경할 때에는 35만큼 수가 증가합니다.

 

10 → Z0으로 변경할 때에는 2번째 자리에서 34만큼 증가합니다.

 

위 과정을 통해 각 36진수를 변경할 때 증가하는 수를 구할 수 있습니다.

 

✭ 1 → Z으로 변경하는 것과 10 → Z0이면, 2번째 자리의 수가 증가하는 것이 훨씬 큽니다.

 

예를 들어,

 

102일 때 1 → Z으로 변경하면 Z02

 

102일 때 0 → Z으로 변경하면 1Z2

 

위 두 예시 중 더 큰 값은 Z02가 됩니다.

 

 

또한 고려해야 하는 요소가 존재합니다.

 

 

각 수를 변경할 때 증가하는 수치가 36이상이면 다음 자리의 수로 올려야 하기 때문입니다.

 

 

만약, 

 

120, 1Z0이 존재할 때 0 → Z으로 변경되면

 

12Z, 1ZZ가 되며, 0이 1번째자리에서 증가하는 수치는 35 + 35 = 70만큼 증가하게 됩니다.

 

36 이상이기 때문에 자릿수 올림을 진행하여 70 / 36 = 1만큼 올리고 남은 값 70 % 36 = 34(Y)가 됩니다.

 

 

점화식으로 표현하면

 

증가하는 수가 36 이상일 때

 

증가하는 수 / 36 = 다음 자릿 수 올림

 

증가하는 수 % 36 = 현재 자리 증가하는 수

 

 

 

 

각 자릿수 기준 36진수의 증가하는 수를 구하였다면 증가하는 폭이 가장 큰 값을 'Z'으로 변경하면 변경하는 최대값을 구할 수 있습니다.

 

→ 그리디 알고리즘, 탐색하지 않고 최대값을 구할 수 있는 방법을 선택합니다.

 

 

 

즉, 증가하는 수치를 비교하여 내림차순으로 정렬해서 K개의 36진수를 고른 뒤 N개의 문자열을 변경한 뒤 36진수의 합을 진행하면 문제에서 원하는 최대값을 구하실 수 있습니다.

 

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N = 5

 

K = 7

 

[N개의 36진수 문자열]

 

GOOD

 

LUCK

 

AND

 

HAVE

 

FUN

 

 

2. 모든 알파벳에 대해서 'Z'으로 변경할 때 증가하는 수를 통해 K개 알파벳을 'Z'으로 변경한 뒤 수를 계산합니다.

 

각 36진수의 증가하는 수치 구하기. 

 

⭐️ (n) : 자릿수

 

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

 

A	B	C	D	E	F	G	H	I	J
25(3)	0	23(2)	22(2),  22(1)	21(1)	20(3)	19(4)	18(4)	0	0

 

K	L	M	N	O	P	Q	R	S	T
15(1)	14(4)	0	12(2), 12(1)	11(3), 11(2)	0	0	0	0	0

 

U	V	W	X	Y	Z
6(3)	5(2)	0	0	0	0

 

 

증가하는 수를 기준으로 내림차순 36진수 정렬

 

{ G, H, L, A, F, O, U, .....}

 

순서대로 K(7)개를 'Z'으로 변경

 

→ 변경되는 36진수 : G, H, L, A, F, O, U

 

변경된 문자열

 

ZZZD

 

ZZCK

 

ZND

 

ZZVE

 

ZZN

 

의 합을 구하면 최대값이 됩니다.

 

 

3. 계산을 통해 얻은 최대 36진수의 값을 결과로 출력합니다.

 

ZZZD + ZZCK + ZND + ZZVE + ZZN = 31YUB

 

 

31YUB 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 36진수를 받을 때 각 36진수가 'Z'으로 변경될 때 증가하는 값을 탐색합니다.
• 각 자릿수 기준 증가하는 값으로 내림차순으로 36진수를 정렬합니다.
• 정렬 기준으로 K개의 값을 선택해서 'Z'으로 변경을 진행합니다.
• 변경된 36진수의 합을 구해서 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //36진수의 증가하는 수치 저장하는 클래스
    static class Info implements Comparable<Info>{
        int idx;
        int[] vals;	//각 자릿수 증가하는 수치

        public Info(int idx, int[] vals){
            this.idx = idx;
            this.vals = vals;
        }

        //각 자릿수 증가하는 수치 기준 내림차순 정렬
        @Override
        public int compareTo(Info o) {
            for(int i=54;i>=0;i--){
                if(this.vals[i] > o.vals[i]){
                    return -1;
                }else if(this.vals[i] < o.vals[i]){
                    return 1;
                }
            }
            return 0;
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String[] words = new String[N];
        
        //36진수 각 자릿수 증가하는 수치 초기화
        List<Info> infos = new ArrayList<>();
        for(int i=0;i<36;i++){
            infos.add(new Info(i, new int[55]));
        }

        //문자열 입락 받은 후, 각 36진수 증가하는 수치 계산
        for(int i=0;i<N;i++) {
            words[i] = br.readLine().trim();
            int len = words[i].length();
            for(int j=0;j<len;j++){
                char c = words[i].charAt(j);
                //'A' ~ 'Z'일 때
                if(c >= 'A'){
                    infos.get(c-'A'+10).vals[len - j - 1] += 'Z' - c;
                }else{		// 0 ~ 9일 때
                    int temp = Character.getNumericValue(c);
                    infos.get(temp).vals[len - j - 1] += 35 - temp;
                }
            }
        }

        //증가하는 수치가 36이상일 때 올림 적용
        for(Info info : infos){
            for(int i=0;i<55;i++){
                if(info.vals[i] >= 36){
                    //올림 적용
                    info.vals[i+1] += info.vals[i] / 36;
                    //남은 값 계산
                    info.vals[i] %= 36;
                }
            }
        }

        int K = Integer.parseInt(br.readLine());
        //각 자릿수 증가하는 수 기준 내림차순 정렬 진행
        Collections.sort(infos);
        //변경해야 하는 값 설정
        Set<Integer> change = new HashSet<>();
        //순서대로 K개 'Z'으로 변경할 36진수 선택
        for(int i=0;i<K;i++){
            change.add(infos.get(i).idx);
        }

        //변경해야 하는 K개 36진수 'Z'으로 변경
        for(int changeVal : change){
            String c;
            if(changeVal >= 10){
                c = String.valueOf((char)(changeVal - 10 + 'A'));
            }else{
                c = String.valueOf((char)(changeVal + '0'));
            }
            for(int i=0;i<N;i++){
                words[i] = words[i].replaceAll(c, "Z");
            }
        }

        int[] result = new int[55];
        //변경한 값에 대해서 36진수의 합 구하기.
        for(int i=0;i<N;i++){
            int len = words[i].length();
            for(int j=0;j<len;j++){
                int temp;
                if(words[i].charAt(j) >= 'A'){
                    temp = words[i].charAt(j) - 'A' + 10;
                }else{
                    temp = Character.getNumericValue(words[i].charAt(j));
                }
                result[len - j - 1] += temp;
            }
        }

        //각 자릿수에 대한 올림 진행
        for(int i=0;i<55;i++){
            if(result[i] >= 36){
                result[i+1] += result[i] / 36;
                result[i] %= 36;
            }
        }
        boolean flag = false;
        //각 자릿수에 맞는 값들을 36진수 형태로 변경
        for(int i=54;i>=0;i--){
            if(result[i] == 0 && !flag){
                continue;
            }
            flag = true;
            if(result[i] >= 10){
                bw.write(String.valueOf((char)(result[i] - 10 + 'A')));
            }else{
                bw.write(String.valueOf(result[i]));
            }
        }
        //만약 결과가 0일 때
        if(!flag){
            bw.write("0");
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
}