[JavaScript] 백준 1038 : 감소하는 수

level : gold 5
문제 링크 : 감소하는 수

1038번: 감소하는 수

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = Number(input);

function subset(arr, num){
    if(num === 1)
        return arr.map(val=>[val]);
    let result = [];
    arr.forEach((value,index)=>{
        const rest = arr.slice(index+1);
        const combi = subset(rest, num - 1);
        const merge = combi.map(v=>[value,...v]);
        result.push(...merge);
    })
    return result;
}

function solution(N){
    let answer = 0;
    let number = new Array(10).fill().map((val,index)=>index.toString());
    let sub = [];
    for(let i = 1; i < 11; i++)
        sub = sub.concat(subset(number,i));
    sub = sub.map(arr => Number(arr.reverse().join(''))).sort((a,b)=>a-b);
    if(N >= sub.length)
        return -1;
    answer = sub[N];
    return answer;
}

console.log(solution(input));

풀이방법
subset function은 arr에 있는 원소들을 기반으로 num만큼 원소를 뽑아 만든 Array들을 모아서 return 해준다.
감소하는 수를 만들기 위해서는 각 자리의 수에 중복된 수가 있으면 안 된다.
그리하여 0~9까지의 수를 string으로 가지는 number라는 Array를 만든다. 숫자들은 오름차순으로 정렬되어있다.
이후에는 number에서 1~10개까지 원소의 개수를 꺼내여 만든 Array들을 sub라는 Array에 담는다.
sub를 map 메서드를 이용하여 각각의 원소 Array를 arr로 명명하고 arr를 뒤집은 뒤 join을 이용하여 숫자를 만든다.
뒤집는 이유는 number이 오름차순으로 정렬하였고 순서대로 조합하여 만들었기에 각 원소 Array들의 원소들은 오름차순 대로 정렬된다. 감소하는 수를 만들어야 하기에 reverse 메서드를 이용하였다.
그 후 sub의 원소들을 오름차순으로 정렬한다.
sub의 length보가 크거나 같으면 감소하는 수를 만들 수가 없기에 -1을 return하고 아니면 N번째 sub의 원소를 return한다.

느낀점
조합 알고리즘을 오랜만에 구현하느라 조금 오래 걸렸다. 평소에도 다시 한번 알고리즘 구현을 습관화해야겠다.