[Java] 백준 10610 30

 

문제

숫자 N이 주어진다.

해당 숫자를 이루고 있는 수들을 이용해서 만들 수 있는 가장 큰 30의 배수를 출력하는 문제이다.

 

 

풀이

처음에는 받아온 N이라는 숫자를 char[]로 쪼개어서,

만들 수 있는 모든 조합을 만들다가 가장 큰 30의 배수가 나오면 출력하게끔 짰다.

근데 NumberFormat Exception이 발생했다.

 

다시 문제를 자세히 살펴보니, 주어진 N이라는 수의 자릿수가 최대 10^5라는 조건이 있었다.

최댓값이 10^5(100_000)라는 것으로 착각했던것.. 

이 조건을 생각하면 long타입으로도 조합을 만들 수가 없다.

 

다른 분들의 코드를 참고해서 풀었다.

풀이의 핵심은 다음과 같다.

- 30의 배수는 10의 배수이므로 끝자리가 0이다.

   => N에 0이 포함되어 있지 않다면 30의 배수를 만들 수 없음 

- 30의 배수는 3의 배수이므로 모든 자릿수를 합했을 때도 3이 나온다.

   => 3의 배수를 나열해보자. 3, 6, 9, 12, 15, 18..... 각 자릿수를 더하면 3의 배수가 나온다는 규칙이 있으므로

   => 이 규칙을 활용해서 조건을 처리한다.

 

 

코드

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

public class Main {

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

        int[] nums = new int[10]; // 0~9까지 각 숫자가 몇 개씩 있는지를 저장
        int sum = 0; 
        for (int i = 0; i < N.length(); i++) {
            int n = N.charAt(i) - '0';
            nums[n]++;
            sum += n;
        }

		// 조건1. 0이 최소 하나 있어야 한다. 
        // 조건2. 자릿수의 총합이 3의 배수여야 한다.
        if (nums[0] == 0 || sum % 3 != 0){
            System.out.println(-1);
            return;
        }

		// 조건이 성립하다면 만들 수 있는 모든 조합이 3의 배수이다.
        // 따라서 큰 숫자부터 거꾸로 더해가며 결과값을 만든다.
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            while(nums[i]-- > 0){
                sb.append(i);
            }
        }

        System.out.println(sb);
    }
}