[BOJ] 10610 30 (js)

문제

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

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

입력

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

출력

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

 

 

핵심 아이디어

단순히 생각하면 permutation을 사용하여 30으로 나누어떨어지는 수를 만들고 그 중에서가 가장 큰 수를 구하면 될 것 같지만.

n이 최대 10^5개의 숫자로 이루어져있으므로, 100000자리의 숫자가 존재하는 것이다.

5자리가 10만단위인데 100000자리는 상상할 수 없이 크기때문에 순열을 사용하는 것은 시간낭비임이 분명하다.

 

이 경우에는 3의 배수의 특징을 사용한다. 각 자리수의 합이 3의 배수이면 그 숫자가 3의배수라는 특징인데,

이 개념을 30배수로 확장시킨다면 쉽게 해결할 수 있다.

(하지만 응용하는 것이 쉽지않아서 나도 풀이를 보고 풀었다.)

즉 ,아래 특성을 잘 이용하면된다.

1. 30의 배수는 3으로 나누어진다.

2. 30의 배수의 1의자리는 0이다

3. 각 자리수의 합이 3의배수이면 3의배수이다.

 

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const solution = (n) => {
    let sum = 0;
    let answer = -1;
    n = Array.from(n);
    n.map((e) => { sum += parseInt(e); })

    if (sum % 3 === 0) {
        n.sort();
        n.reverse();
        if (n[n.length - 1] === '0') {
            answer = n.join("");
        }
    }
    console.log(answer);
}

const input = [];
rl.on("line", function(line) {
    input.push(line);

}).on("close", function() {
    const n = input[0]

    solution(n);
    process.exit();
});