[JavaScript] 백준 1038 감소하는 수 (JS)

쇠막대기

📚 문제 설명

자연서 X의 모든 자릿수가 내림차순으로 되어있으면 감소하는 수라고 한다.
예를들어 321과 950은 감소하는 수지만, 322와 956은 감소하는 수가 아니다.

0은 0번째 감소하는 수이고 1은 1번쨰 감소하는 수라고 할 때, N 번째 감소하는 수를 찾으시오.

만약 불가능하다면 -1을 리턴.

👨🏻‍💻 풀이 과정

이 문제를 읽고 가장 처음 들었던 의문은 '왜 불가능이 있지?' 였다.
생각해 보면 아주 간단하다. 숫자는 0부터 9까지이기 때문에 9876543210 이 마지막 감소하는 숫자가 되기 때문이다.

그럼 이제 어떻게 감소하는 수를 찾을까 고민해보면, 0부터 9까지의 숫자를 조합하면 그 숫자는 감소하는 숫자가 될 수 있다.
단순하게 i 개의 숫자를 뽑아서 내림차순으로 정렬하면 그 숫자는 감소하는 수가 되기 때문이다.

따라서 우선 Target개의 자릿수의 숫자 조합을 구하는 함수 Combination을 구현했다.

Combination 함수 코드

    const Combination = (Arr, Index, Target) => {
      	// Target만큼의 숫자를 뽑았다면 종료.
        if (Arr.length === Target) {
            CombiArr.push(parseInt(Arr.sort((a,b) => b-a).join('')));
            return;
        }
      	// 이미 뽑은 숫자를 제외하고 나머지 중에서 선택.
        for (let i = Index; i < 10; i++) {
            Combination([...Arr, i], i + 1, Target);
        }
    };

이렇게 Combination 코드를 구현하고 보니 불필요한 부분이 눈에 보였다.
parseInt(Arr.sort((a,b) => b-a).join(''))
바로 이 부분인데 어차피 숫자를 순차적으로 뽑으며 이전의 뽑은 수와 비교하여 조합을 진행한다.
따라서 for문의 조건을 조금 변경하면 sort를 할 필요가 없어 보인다.

Combination 함수 수정

    const Combination = (Arr, Index, Target) => {
        if (Arr.length === Target) {
            CombiArr.push(parseInt(Arr.join('')));
            return;
        }
      	// 큰 수부터 순서대로 조합.
        for (let i = Index; i >= 0; i--) {
            Combination([...Arr, i], i - 1, Target);
        }
    };

사실 이렇게 조합을 진행하면 나머지 과정은 매우 간단하다.
앞서 말했듯 자릿수가 10개인 경우가 최대이기 때문에 자릿수 1개부터 10개인 경우까지 조합을 진행한 후에
sort를 이용해 정렬하여 N 번째 숫자를 출력하면 된다.

불가능할 경우 -1을 출력해야 하기 때문에 10자리까지 조합한 배열의 크기를 구해보니 1023이 나왔다.
따라서 9876543210 이라는 숫자는 1022번째 숫자임을 알 수 있고,
1022보다 크면 -1을 리턴하면 된다.

전체 코드

let fs = require("fs");
let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
let CombiArr = [];
const Combination = (Arr, Index, Target) => {
    if (Arr.length === Target) {
        CombiArr.push(parseInt(Arr.join('')));
        return;
    }
    for (let i = Index; i >= 0; i--) {
        Combination([...Arr, i], i - 1, Target);
    }
};

const solution = () => {
    for (let i = 1; i <= 10; i++) {
        Combination([], 9, i);
    }
    CombiArr.sort((a, b) => a - b);

    if (N > 1022) {
        console.log(-1);
    } else {
        console.log(CombiArr[N]);
    }
};

solution();

🧐 후기

문제를 읽고 당연하게 가장 먼제 생각난 것을 모든 조합을 다 배열에 저장한 후에 값을 구하는 방법이었다.
그런데 그 방법이 아무리 생각해도 아닌 것 같아서 고민하다가 다른 코드를 살펴보았는데 다들 그냥 다 구하는 것을 보고 처음 생각한대로 그냥 구현했다.
사람에 따라서 0부터 9까지의 숫자를 2진법으로 생각하여 총 10자리의 2진법 숫자를 이용해 푸는 사람도 있었다.
그러나 개인적으로 좀 이해하기 어려워서 굳이 그 풀이로 풀어보진 않았다.