그리디: 백준 10610 자바(Java) 30

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

10610번: 30

풀이:

미르코가 원하는 30의 배수가 되는 가장 큰 수를 찾기 위해서는

1. 맨 끝 숫자는 '0' 이어야 한다.
2. 각 자리 수의 합이 3으로 나누어 떨어져야 한다.

이 두 가지 조건을 만족해야 한다.

먼저 입력받을 N은 10^5개의 숫자로 이루어져 있기 때문에 int 자료형의 범위를 벗어난다.

그렇기 때문에 문자열로 입력받은 후 크기가 10인 배열을 만들어 이 배열에 입력받은 수의 정보를 넣어주는 방식으로

코드를 작성해야 한다. 

 

위 30의 배수가 되기 위한 조건을 만족한다면 큰 수부터 출력되도록 반복문을 작성해준다.

조건을 만족하지 않는다면 -1을 출력해주면 된다.  

 

정답:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();

        int[] num = new int[10];
        int len = N.length();
        int total = 0;

        for (int i = 0; i < len; i++) {
            int temp = Integer.parseInt(N.substring(i, i + 1));
            num[temp] += 1;
            total += temp;
        }

        if (N.contains("0") && total % 3 == 0) {
            for (int i = 9; i >= 0; i--) {
                while (num[i] > 0) {
                    System.out.print(i);
                    num[i]--;
                }
            }
        } else {
            System.out.println(-1);
        }
    }
}