백준 10974번: 모든 순열 - javascript

백준 10974번: 모든 순열

문제 설명

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

접근

보자마자 백준 N과M이랑 뭐가 다르지? 하는 생각이 든 문제다.
그냥 중복을 허용하지 않는 모든 순열을 출력하면 된다.

이 문제에 대해 2가지 방법이 있다고 생각한다.
먼저 위에서 언급한 N과M 문제 스타일로 중복체크하면서 N만큼의 깊이의 순열들을 만들어서 출력하는 방법, 그리고 백준 10972번의 다음 순열을 구하는 방법을 이용해서 1 2 3 … N-1 N 의 순열부터 시작하는 방법.

주어진 N의 최대값이 8이길래 그냥 N과 M의 코드를 고대로 썼다…
해당 풀이를 참고하실분은 여기로…

다만 N의 범위가 다음 순열과 같이 막 10,000까지 주는 문제의 경우라면 당연히 메모리가 제한되는 문제니깐 결국 그냥 brute force로 일일히 NxN만큼 순열생성을 해주는게 정답아닌가? 하는 생각이 들긴한다…

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
let list = [];
let result = [];
let check = new Array(9).fill(false);
rl.on('line', function (line) {
  input.push(line);
})
  .on('close', async function () {
  // 답안 작성
  let answer =0;  
  let n = input[0];  
  re(0,n,n);
  console.log(result.join('\n'));
  process.exit();
});

let re = function(cnt,n,m){
  if(cnt==m){
    result.push(list.join(' '))
    return 1;
  }
  for(let i=1;i<=n;i++){
    if(!check[i]){
      check[i] = true;
      list[cnt] = i;
      re(cnt+1,n,m);
      check[i] = false;
    }
  }
  return 1;
}