[BaekJoon] #10610 - 30 [Java][C++]

문제 링크

---

1. 아이디어

주어진 수를 구성하는 숫자들의 순서를 변경해서 30의 배수가 될 수 있으면 주어진 수의 각 숫자들의 조합으로 가장 큰 수를 만들고 아니면 -1을 출력하는 문제로 30의 배수는 3의 배수이면서 10의 배수라는 점을 활용하면 해결할 수 있다. 3의 배수는 각 자릿수의 합이 3의 배수이면 3의 배수이고 10의 배수는 마지막 자리가 0이면 10의 배수가 된다. 숫자들을 어떻게 배치하든 항상 3의 배수가 되며 0이 마지막 자리에만 오면 되므로 주어진 숫자들을 내림차순으로 배치한 수는 가장 큰 수가 되면서 30의 배수가 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log N)$	$O(N)$

($N$ = s의 길이)

---

3. 코드

풀이 [Java][C++]

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

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

        String s = br.readLine();
        int sum = 0;
        boolean has0 = false;

        for (char c : s.toCharArray()) {
            sum += c - '0';
            if (c == '0') has0 = true;
        }

        if (sum % 3 == 0 && has0) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);

            for (char c : arr) {
                sb.append(c);
            }
            sb.reverse();
        } else {
            sb.append(-1);
        }

        System.out.println(sb);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int sum = 0;
    bool has0 = false;

    for (char c : s) {
        sum += c - '0';
        if (c == '0') has0 = true;
    }

    if (sum % 3 == 0 && has0) {
        sort(s.rbegin(), s.rend());
        cout << s;
    } else {
        cout << -1;
    }
}

---