문제

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

N개의 자연수 중에서 M개를 고른 수열

입력

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

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

출력

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

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

예제 입력

4 2
9 7 9 1

예제 출력

1 7
1 9
7 1
7 9
9 1
9 7
9 9

내가 했던 풀이 방법

1. visited 배열을 N 크기로 설정하고 false로 초기화한다.
2. DFS를 이용하여 N개에서 M개를 선택하는 경우를 찾는다. 해당 경우를 찾았다면 set에 문자열 형태로 저장한다. (중복되는 경우를 제거하기 위함)
3. DFS 연산 이후 set에 저장된 데이터를 Array로 변환한다. sort를 이용해, 사전순으로 정렬한다. (각각의 문자열을 공백으로 분할하여 Number형 배열로 저장하고, 앞에 위치한 숫자가 더 작은 것부터 순차적으로 정렬한다.)
4. 정렬된 배열을 출력한다.

코드

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

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);

element = element.trim().split(' ').map(Number);

let set = new Set();
function DFS(depth, sequence, visited) {
  if (depth === M) {
    set.add(sequence.join(' '));
    return;
  }

  for (let i = 0; i < element.length; i++) {
    if (!visited[i]) {
      visited[i] = true;
      DFS(depth + 1, [...sequence, element[i]], visited);
      visited[i] = false;
    }
  }
}

let visited = Array.from({ length: N }, () => false);
for (let i = 0; i < element.length; i++) {
  visited[i] = true;
  DFS(1, [element[i]], visited);
  visited[i] = false;
}

let sorted = Array.from(set);
sorted.sort((a, b) => {
  let num1 = a.split(' ').map(Number);
  let num2 = b.split(' ').map(Number);

  for (let i = 0; i < M; i++) {
    if (num1[i] < num2[i]) return -1;
    else if (num1[i] > num2[i]) return 1;
  }
});

console.log(sorted.join('\n'));

회고

사전순을 맨날 헷갈린다... 사전순이라 해서 sort만 하면 되겠네...했는데 틀렸네..