[알고리즘 연습] 백준 1174 (줄어드는 수, 자바스크립트)

문제

1174번: 줄어드는 수

---

풀이

• 숫자는 반드시 줄어들어야 하기 때문에 arr는 9부터 0까지 역순으로 저장한다.
• 조합 알고리즘을 사용하여 1자리부터 10자리까지의 줄어드는 수를 모두 구한다.
• 줄어드는 수를 모두 구한 뒤 저장한 배열을 오름차순 정렬하면 N번 째 수를 쉽게 구할 수 있다.
• N이 구할 수 있는 숫자의 범위를 초과하는 경우 -1를 출력한다.

소스 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const N = +input[0];
const arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]; // 숫자는 반드시 줄어들어야 한다.
const visited = new Array(10).fill(false);
const result = [];
const answer = [];

for (let i = 1; i <= 10; i++) {
  dfs(0, 0, i);
}

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

console.log(answer[N - 1] ?? -1);

function dfs(start, idx, len) {
  if (idx === len) {
    let cand = 0;

    for (const num of result) {
      cand *= 10;
      cand += num;
    }

    answer.push(cand);
    return;
  }

  // 조합 알고리즘
  for (let i = start; i < 10; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    result.push(arr[i]);
    dfs(i + 1, idx + 1, len);
    result.pop();
    visited[i] = false;
  }
}