알고리즘 풀이 - 백준 10610(30, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

최대 100,000개의 숫자로 이루어진 숫자 N은 0으로 시작하지는 않을 때, 30의 배수가 되는 가장 큰 수를 만들어 출력하는 문제

 

 

2. 풀이

 

문제를 잘 이해하자. 100,000까지의 숫자가 아니라, 100,000개의 숫자이다. 즉, 1~9까지의 숫자가 최대 100,000개 있을 수 있다는 의미이다.

당연히 단순 반복문을 통해서 30으로 나누어떨어지는 지 등을 구해서 해결할 수는 없다.(숫자가 너무 큰 데다가, 시간도 오래 걸림)

 

간단하게 생각해보자. 30으로 나누어 떨어지려면 어떻게 해야 할까?

30은 소인수 분해를 하면 2 x 3 x 5 가 된다. 여기서 2 x 5를 하면 10이 되는데 이 의미는 반드시 1의 자리수가 0이 되어야만 30으로 나눌 수 있다는 뜻이다.

그리고 1의 자리수가 0이라면 3으로만 나누어떨어진다면 30배수가 될 수 있다! 3으로 나누어 나머지가 0이 되는 것은 각 자리수를 모두 더한 값이 3으로 나누었을 때 나머지가 0이 되면 된다는 규칙이 있다.

 

즉, 아래의 규칙을 이해하자.

① 주어진 100,000자리의 숫자의 1의 자리수가 0이어야 한다.
② 주어진 100,000자리의 숫자의 각 자리수를 모두 합한 값이 3으로 나누어 떨어져야 한다.

 

위 규칙을 통해 코드로 구현해보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n = br.readLine();
        
        List<Integer> list = new ArrayList<>();
        long sum = 0;
        
        // 주어진 수를 입력받아 List에 넣고 각 수의 합 또한 별도로 저장한다.
        for(int i=0; i < n.length(); i++){
            int num = n.charAt(i) - '0';
            sum += num;
            list.add(num);
        }
        
        // 정렬 수행(오름차순)
        Collections.sort(list);
        
        StringBuilder sb = new StringBuilder();
        
        // 0이 반드시 있어야 하며, 전체 합이 3으로 나누어 떨어지는 경우에만 30이 될 수 있다.
        // 즉, 아래 조건이 만족되면 그대로 출력을 수행하고 안되는 경우 -1을 출력한다.
        if(list.get(0) == 0 && sum % 3 == 0){
            for(int i=list.size()-1; i >= 0; i--){
                sb.append(list.get(i));
            }
        } else {
            System.out.println(-1);
            return;
        }
        System.out.println(sb);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.