[백준 10610] - [그리디알고리즘] - 30 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/10610

---

이 문제는 그리디 알고리즘 문제 중에서 어려운 편에 속하는 문제이다. 

문제 자체에 오해 할 수 있는 요소가 존재해서 다들 잘못 이해 하고 접근하다가 계속 틀리다는 결과를 받는거 같다.

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

입력값 은 최대 10^5 의 숫자라고 하는게 100000 까지 입력을 받는게 아니라 자리수가 10^5개라는 말이었다. 

대부분의 사람들도 100000 까지만 입력 받는걸로 이해하고 문제를  접근해서 고생을 한 거 같다. 

정수형 타입인 int 나 실수형 타입인 long 이나 10^5개의 자리수를 입력 받을 수 있는  자료형은 없다.

그럼 어떻게 문제를 풀어야 할까? 

입력 자체를 문자열 타입으로 받으면 문제는 해결된다. 

999999999900000000000000000999999999999999999 의 숫자를 입력 받았을경우 절때 int 나 long으로는 값을 입력받을 수 없기 때문이다. 

문자열로 입력을 받은 뒤에 Substring으로 각 자리수를 잘라가면서 0부터 9까지 각 숫자가 몇개로 조합됐는지 확인한다.

strLen = str.length(); numCountArr = new int[10]; long total = 0; for(int i=0; i < strLen; i++) { int tNum = Integer.parseInt(str.substring(i, i+1)); numCountArr[tNum] += 1; total+=tNum; }

입력을 받았다면 입력받은 데이터가 유효한 숫자인지 확인하면 된다. 

30의 배수인지 확인하는 방법은 어떻게 될까?

조건 1) 0 이 있어야 한다.

30의 배수는 무조건 뒤에 최소한 한개 이상의 0을 가지고 있다. 

입력 받은 수 자체에 0이 존재하지 않다면? 그 수는 유효하지 않은 수이기 때문에 -1을 출력해주고 프로세스를 종료시키면 된다.

조건 2) 각 자리수의 합이 3의 배수여야 한다.

이 조건은 이해하기가 힘든데 3의 배수를 표로 그려서 확인해보면 이해하기 쉽다. 

3 * 1	3	3 * 11	33
3 * 2	6	3 * 12	36
3 * 3	9	3 * 13	39
3 * 4	12	3 * 14	42
3 * 5	15	3 * 15	45
3 * 6	18	3 * 16	48
3 * 7	21	3 * 17	51
3 * 8	24	3 * 18	54
3 * 9	27	3 * 19	57
3 * 10	30	3 * 20	60

위의 표는 3의 배수를 60까지 구해본 표이다.

각 3의 배수의 결과들의 모든 자리수를 더해보면 그 수들 또한 3의 배수이다. 

// 0이 존재하지 않으면 30 배수 조차도 될 수 없다. // 각 자리수의 총 합이 3의 배수가 아니면 종료해야한다. if(!str.contains("0") || total % 3 != 0) { System.out.println("-1"); return; }

그렇다면 조건 1과 조건 2를 모두 만족한다면 입력 받은 수는 30의 배수가 될 수 있다는 말이다. 

입력값에 대한 0부터 9 까지의 각 숫자의 개수를 가지고있는 배열을 9부터 0까지 전부 문자열에 합해주면 결과를 출력할 수 있다.

StringBuilder sb = new StringBuilder(); for(int i = 9; i >= 0; i--) { while(numCountArr[i] > 0) { sb.append(i); numCountArr[i]--; } }

소스

import java.util.Scanner;
 
public class Main {
    public static final int MAX = 100000;
    
    public static String str;
    public static int[] numCountArr;
    public static long strLen;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        str= sc.nextLine();
        
        strLen = str.length();
        numCountArr = new int[10];
        long total = 0;
        for(int i=0; i < strLen; i++) {
            int tNum = Integer.parseInt(str.substring(i, i+1));
            numCountArr[tNum] += 1;
            total+=tNum;
        }
        
        // 0이 존재하지 않으면 30 배수 조차도 될 수 없다.
        // 각 자리수의 총 합이 3의 배수가 아니면 종료해야한다.
        if(!str.contains("0") || total % 3 != 0) {
            System.out.println("-1");
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 9; i >= 0; i--) {
            while(numCountArr[i] > 0) {
                sb.append(i);
                numCountArr[i]--;
            }
        }
        System.out.println(sb.toString());
    }
}