[BOJ] 10610 - 30 JAVA

www.acmicpc.net/problem/10610

10610번: 30

문제

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

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

입력

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

출력

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

예제 입력 1

30

예제 출력 1

30

예제 입력 2

102

예제 출력 2

210

예제 입력 3

2931

예제 출력 3

-1

예제 입력 4

80875542

예제 출력 4

88755420

 

 

 

 

 

 

 

 

풀이 .

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        String n = br.readLine();
        int[] cnt = new int[10];

        long total = 0;
        for(int i = 0; i < n.length(); i++) {
            int temp = n.charAt(i) - '0';
            cnt[temp] += 1;
            total += temp;
        }

        // 30의 배수는 10의 배수이면서 3의 배수이다
        // 10의 배수는 반드시 0을 하나 이상 가져야 한다
        // 3의 배수이려면 모든 자리수의 합이 3의 배수여야 한다
        if(!n.contains("0") || total % 3 != 0) {
            bw.write("-1");
            br.close();
            bw.flush();
            bw.close();
            return;
        }

        // 큰 수부터 그 개수를 찍어준다
        for(int i = 9; i >= 0; i--) {
            for(int j = 0; j < cnt[i]; j++) {
                sb.append(String.valueOf(i));
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

 

처음 봤을 때는 모든 조합을 구해서 체크하는 것인가 했지만 절대 그럴 수 없다.

 

입력받는 문자의 길이가 10^5이기 때문에 무조건 시간초과이다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

30의 배수는 10의 배수이면서 동시에 3의 배수이다.

 

1. 반드시 0을 포함 해야한다. (10의 배수 조건)

2. 모든 자리의 수를 더하면 3의 배수가 되어야 한다. (3의 배수 조건)

 

30의 배수가 될 수 없는 조건을 체크하여 예외처리를 먼저 한다.

 

예외처리를 통과하고 나면 어차피 전부 3의 배수이므로 가장 큰 순서부터 보유한 개수만큼 하나씩 출력하면 된다.