그리디 - 30

백준 링크 : https://www.acmicpc.net/problem/10610

문제 :

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

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

출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

문제를 풀기전 항상 생각해야 하는 것들 :

1. 어떤 알고리즘을 사용할 것인가 ?

2. 최대한 구체적으로 구상하기

3. java로 풀 경우 int 값을 벗어나는가 ?

1. 3의 배수는 각 자리의 수의 합이 3의 배수이다. 즉 3의 배수인지를 구하려면 각자리수를 더한 후 3으로 나누었을 때 나머지가 0이나와야한다. 또한 이문제는 30의 배수를 구하는 것이기 때문에 무조건 0이 하나 포함되어야 한다.

2. 먼저 0부터 9까지의 수이기 때문에 int [10] 배열을 선언 후 각 자리수의 숫자가 어떤 것인지 카운트해주면서 총합을 구한다. 그리고 int[0] 이 있는지 없는지 확인하고, 총합이 3 으로 나누었을 때 나머지가 남는지 확인한다. 0이 없거나 나머지가 있다면 -1
   그리고 StringBuilder 사용하여 뒤에 숫자부터 더해준다.

3. 문자열로 나타낼 것이기 때문에 상관없음

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int sum = 0;
		int[] nums = new int[10];
		for(int i = 0 ; i < str.length(); i++) {
			int num = Integer.parseInt(str.substring(i, i+1));
			nums[num]++;
			sum += num;
		}
		if(sum % 3 != 0 || nums[0] <= 0) {
			System.out.println(-1);
			return;
		}

		StringBuilder sb = new StringBuilder();
		for(int i = 9 ; i >= 0; i--) {
			for(int j = 0 ; j < nums[i]; j++) {
				sb.append(i);
			}
		}
		System.out.println(sb.toString());
		
	}

}