📍문제 링크
https://www.acmicpc.net/problem/15666
15666번: N과 M (12)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
📍알고리즘 분류
- 백트래킹
📍문제 풀이
- 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 객체를 통해 중복을 제거하는 것이 시간적으로 빠르다