[백준][백트래킹] 10974 모든 순열 NodeJs 구현

     

목차

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

문제

 

 

 

문제 구현 방향

처음에 순열을 재귀로 구현했다가 틀렸다..

재귀를 한후 정렬하는 과정에서 시간초과가 나기 때문이다.

 

 

잘못된 코드

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];
let arr = [];
for (let i = 1; i <= N; i++) {
  arr[i] = i;
}
function swap(a, b) {
  let tmp = arr[a];
  arr[a] = arr[b];
  arr[b] = tmp;
}
let Sr = [];
function permutation(n, r, depth) {
  if (depth === r) {
    Sr.push(arr.slice(1));
  }
  for (let i = depth; i <= n; i++) {
    swap(arr[i], arr[depth]);
    permutation(n, r, depth + 1);
    swap(arr[i], arr[depth]);
  }
}
permutation(N, N, 1);

Sr.sort((a, b) => {
  let cnt = 0;
  while (cnt < Sr.length) {
    if (a[cnt] !== b[cnt]) {
      return a[cnt] - b[cnt];
    } else {
      cnt++;
    }
  }
});

Sr.forEach((item) => console.log(...item));

 

 

코드 구현

const input = require("fs")
  .readFileSync("/dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];
let arr = [];
let visited = Array(N + 1).fill(false);

function permutation(depth) {
  if (depth === N) {
    console.log(...arr);
    return;
  }
  for (let i = 1; i <= N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      arr.push(i);
      permutation(depth + 1);
      arr.pop();
      visited[i] = false;
    }
  }
}

permutation(0);