[백준] 10610번 : 30 – JAVA [자바]

[Silver IV] 30 - 10610

문제 링크

성능 요약

메모리: 29736 KB, 시간: 600 ms

분류

그리디 알고리즘, 수학, 정수론, 정렬, 문자열

문제 설명

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

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

입력

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

출력

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

 

---

문제풀이

이 문제는 30의 배수를 만족하는 가장 큰 수를 만들 조건을 생각하면 된다.

1. 입력받은 수를 내림차순으로 정렬한다.
2. 각 요소의 합이 3의 배수여야 한다.
3. 10의 배수가 되기 위해 일의자리 숫자가 0이어야 한다. (0이 입력받은 수에 포함)

---

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String[] data = sc.nextLine().split("");

        // 내림차순으로 출력
        Arrays.sort(data, Collections.reverseOrder());
        StringBuffer sb = new StringBuffer();

        int sum = 0;
        int isZero = 0;
        for (String each : data) {
            sum += Integer.parseInt(each);
            sb.append(each);
            if(Objects.equals(each, "0")){
                isZero++;
            }
        }
        if(isZero > 0 && sum % 3 == 0){
            System.out.println(sb);
        }else System.out.println(-1);
    }
}