문제

<aside> 🌐

백준 10947번 - 모든 순열

</aside>

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

입력

1 ≤ N ≤ 8

3

출력

모든 순열을 사전순으로 출력한다.

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

문제 풀이

즉, 1부터 N까지의 모든 숫자로 만들 수 있는 모든 나열을 순서대로 출력해야하므로 순열 문제입니다.

재귀적으로 풀면 자연스럽게 사전 순으로, 중복 없이 출력할 수 있습니다.

• 1 ~ N 까지의 숫자를 사용해서

for(let i = 1; i <= N; i++){ ... }

• 현재까지 만든 순열 배열을 하나씩 채우되,

const visited = Array(N + 1).fill(false);
const path = [];

• 숫자가 겹치지 않도록 체크하고

if (visited[i]) continue; // 사용한 적이 있다면 넘어가고,

// 사용한 적이 없다면
visited[i] = true; // 사용 표시를 하고
path.push(i); // 추가해서
getCombinations(); // 순열을 구하고
path.pop(); // 제거하고
visited[i] = false; // 사용 표시를 해제합니다.

• 길이가 N이 되면 출력하도록 합니다.

if(path.length === N) {
	console.log(path.join(' '));
	return;
}

전체 코드

const fs = require("fs");
const N = Number(fs.readFileSync("/dev/stdin").toString().trim());

const visited = Array(N + 1).fill(false);
const path = [];

function getCombinations() {
  if (path.length === N) {
    console.log(path.join(" "));
    return;
  }

  for (let i = 1; i <= N; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    path.push(i);
    getCombinations();
    path.pop();
    visited[i] = false;
  }
}

getCombinations();