백준1038번 - 감소하는 수 자바스크립트(Node.js)풀이

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

 

 

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

 

 

 

문제유형

브루트포스 알고리즘

백트래킹

 

---

 

백줄이 넘어가는 정말 보기힘든 코드로 풀고있다가 너무나도 신박한 풀이를 발견하였다.

이 풀이를 nodejs 코드로 변환하고 산책을 하면서 코드를 이해해보았다.

 

 

encrypted-def/BOJ

 

 

1. 1023

이 문제의 입력 최대치는 1,000,000 이지만, 실제로 사용될 수 있는 입력의 수는 1023개이다.

그 이유는 이 문제가 10진수의 감소하는 수이기 때문이다. 10진수에서는 총 10가지의 수만을 이용할 수 있기에, 이 상황에서 나올 수 있는 최대값은 '9876543210'이다. 이는 총 10자리수이며 첫번째 자리에서 나올수 있는 경우의수는 9로 한가지만 존재한다. 왜냐하면 10진수에서 첫번째 자리 수에 9이외에 다른 숫자가 오는 감소하는 수는 존재하지 않기 때문. 같은 이유로 두번째 자리에는 2가지의 숫자만 올 수 있고, 세번째 자리에는 3가지의 숫자만 올 수 있다. 이를 바탕으로 이 문제에서 발생할 수 있는 감소하는 수는 총 1023개인것을 알 수 있다.

(10C1 + 10C2 ... 10C10 = 2^10 또는 원소가 10개인 집합의 부분집합의 갯수)

 

2. 감소하는수 만들기

위에서 나올수 있는 경우의 수는 1023가지라는것을 알았다. 그럼 이를 바탕으로 감소하는수를 구해보자.

for(let i=1; i<=1023; i++){
    let num = 0;
    let tmp_i = i;
    for(let idx = 9; idx >=0; idx--){
        if(tmp_i % 2 == 1){
            num = 10 * num + idx;
        }
        tmp_i = Math.floor(tmp_i/2);
    }
    if(i <= 20)
        console.log(num, i);
    decnum.push(num);
}

이렇게 1023개의 감소하는 수를 구할 수 있다. 1023이라는 수를 이진수로 생각하면 쉽게 이해할 수 있다.

 

 0부터 1023까지의 수는 10자리의 2진수로 변환할 수 있으며, 최상위비트를 0, 최하위비트가 9와 치환된다고 생각해보자. 그럼 아래와 같이 나타낼 수 있다.

 

0123456789 (각 자리의 id)

0000000000 (2진수)

 

 이렇게 이진수로 표현하면 중복없이 0부터 9로 이루어진 수들을 만들 수 있다는 것을 쉽게 알 수 있으며, 이진수에서 1에 해당하는 id값들을 뒤에서부터 순서대로 적으면 감소하는 수가 된다.

 

 

3. sort

 이 문제에서는 사용자 입력에 해당하는 n번째 감소하는 수를 구해야한다. 하지만 2번에서 구한 감소하는 수는 순서대로 정렬되어있지 않다. (입력이 1인경우 9가 나오고, 2인경우 8이 출력된다) 이는 감소하는 수 리스트에 있는 모든 원소들을 정렬함으로써 해결할 수 있다.

 

 

 

 

전체코드

const fs = require('fs');
const stdin = (process.platform === 'linux'
        ? fs.readFileSync('/dev/stdin').toString()
        : `18`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

let decnum = [];
//10C1 + 10C2 + ... 10C10 = 2^10 - 1 = 1023
for(let i=1; i<=1023; i++){
    let num = 0;
    let tmp_i = i;
    for(let idx = 9; idx >=0; idx--){
        if(tmp_i % 2 == 1){
            num = 10 * num + idx;
        }
        tmp_i = Math.floor(tmp_i/2);
    }
    if(i <= 20)
        console.log(num, i);
    decnum.push(num);
}

decnum.sort( (a,b) => a-b);

let N = parseInt(input());
if(N > 1022){
    console.log(-1);
}
else{
    console.log(decnum[N]);
}