백준 15666 < N과 M (12) > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

 

📍알고리즘 분류

- 백트래킹

 

📍문제 풀이

- N개의 중복을 허용하는 수가 주어질 때, 중복을 허용하여 M개를 고르는 경우의 수를 모두 출력한다 (중복조합)

- 비내림차순으로 출력한다 (오름차순 + 중복 허용)

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [N, M] = in1.split(" ").map(Number);
const data = in2
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);

const result = [];
const answer = new Set();

const recursive = (depth) => {
  if (depth === M) {
    const res = result.join(" ");
    answer.add(res);
    return;
  }

  for (let i = 1; i <= N; i++) {
    if (depth > 0 && result[depth - 1] > data[i - 1]) continue;
    result[depth] = data[i - 1];
    recursive(depth + 1);
  }
};

recursive(0);
console.log([...answer].join("\n"));

 

📍리뷰

- depth === M 일때 중복을 검사하는 조건문을 추가하는 것 보다 Set 객체를 통해 중복을 제거하는 것이 시간적으로 빠르다