문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력

4 2
9 8 7 1

예제 출력

1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

내가 했던 풀이 방법

1. 입력받은 N들을 정렬한 뒤, 일반적인 백트래킹 방법을 사용한다. 그 뒤 arr에 담긴 수열을 sort를 하여 set에 저장해 중복을 제거하고 비내림차순으로 출력할 수 있게 한다. -> 실패 (시간초과) sort를 두 번이나 하는 게 문제가 된다고 생각.

2-1. 입력받은 N을 number 배열에 Number형으로 저장한 뒤, 오름차순으로 정렬해준다.
2-2. start와 depth를 0으로 하는 DFS를 호출한다. (start를 통해 sort를 한 번만 사용하게 되어 속도를 개선하였다. start로 sort를 없앨 수 있는 이유는 이미 number에는 정렬이 되어있기 때문에 이전에 사용한 number보다 이후에 사용할 number가 더 큰 상태이다. 즉, start를 통해 이전 number를 사용하지 않도록 제한해주면 오름차순이 자연스럽게 만들어지기 때문이다.)
2-3. DFS에서는 depth가 M일 경우, arr에 있는 요소들을 공백으로 join하여 set에 저장해준다. M이 아닐 경우, start부터 N-1까지 i를 1씩 증가시키면서 number[i]를 arr에 넣어준다. 현재 i값을 start로 하고, depth를 1 증가시킨 DFS를 호출한다. DFS가 return되면 현재 arr에 마지막 요소를 삭제시켜주고 2-3을 반복해준다.
2-4. set에 저장된 값을 forEach를 통해 answer에 저장해준다. 저장할 때는 수열마다 \n을 추가하여 줄바꿈을 추가해준다.

코드

const fs = require('fs');
let [n, input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

const N = parseInt(n.trim().split(' ')[0]);
const M = parseInt(n.trim().split(' ')[1]);

let number = input.trim().split(' ').map(Number);
number.sort((a, b) => a - b);
let set = new Set();
let arr = [];

DFS(0, 0);
let answer = '';
set.forEach((value) => {
  answer += value + '\n';
});
console.log(answer.trim());

function DFS(start, depth) {
  if (depth === M) {
    set.add(arr.join(' '));
    return;
  }

  for (let i = start; i < N; i++) {
    arr.push(number[i]);
    DFS(i, depth + 1);
    arr.pop();
  }
}

회고

N과 M 문제를 처음 접하고 백트래킹에 대한 지식이 없다 생각해 백트래킹에 대해 공부한 뒤 여러 N과 M 문제를 풀이했다. 4번까지 풀이하고 이정도면 백트래킹에 어려움은 없겠다 생각해 8번으로 점프했는데 예상보다 어려웠던 문제.. 중복을 제거한다는 게 단순히 똑같은 배열이 아닌 같은 요소가 같은 수로 사용된 경우도 제외해주어야 한다고 하니까 너무 복잡해졌다. (실제로 구현하는 결과는 단순했지만 처음 받아들였을 때는 난잡하게 생각했다.) 역시 순서대로 좀 더 풀이하고 했어야 했을까... 내가 아는 것에 정말 다 아는지 자만하지 말아야겠다. 물론 이번 문제는 백트래킹을 구현하는 것보다 중복/오름차순을 구현하는 게 오래걸린 문제이긴 하지만!