모든 순열

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 10972번 - 다음 순열 풀이 에서 알아 봤듯이 모든 순열을 구하는 것은 모든 경우를 따져보는 BruteForce 알고리즘과 유사합니다.
  • 첫 순열에서 다음 순열을 찾는 알고리즘을 N! 만큼 반복하면 모든 순열을 구할 수 있습니다.
  • 마지막 순열에 도달하면 반복은 끝나게 됩니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = Array(n)
		.fill(0)
		.map((v, i) => v + i + 1);

	// 첫 순열 출력
	let res = `${arr.join(" ")}\n`;

	// N! 번 만큼 반복
	while (true) {
		// ? 찾기
		let i = n - 1;
		for (i = n - 1; i > 0; i--) {
			if (arr[i - 1] > arr[i]) continue;

			break;
		}

		// 마지막 순열인 경우
		if (!i) break;

		// ? 보다 한 단계 큰 수 찾기
		let j = n - 1;
		for (j = n - 1; j > i - 1; j--) {
			if (arr[j] < arr[i - 1]) continue;

			break;
		}

		// SWAP
		[arr[i - 1], arr[j]] = [arr[j], arr[i - 1]];

		// ? 이후 내림 차순을 오름 차순으로 뒤집기
		j = n - 1;
		while (i < j) {
			[arr[i], arr[j]] = [arr[j], arr[i]];
			i += 1;
			j -= 1;
		}

		res += `${arr.join(" ")}\n`;
	}

	return res;
};

console.log(solution(input));

다른 방식의 문제 풀이 step 1

  • 백준 15649번 - N과 M (1) 풀이 를 이용해서도 풀 수 있습니다.
  • 1 ~ N 까지의 자연수 중에서 중복없이 M 개를 골라야하는데 순서에 맞게 고르면 모든 순열을 구할 수 있습니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const rec = (n, res, step, visited, depth) => {
	if (depth === n) {
		res.push(step.join(" "));
		return;
	}

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

		visited[i] = true;
		step.push(i);
		rec(n, res, step, visited, depth + 1);

		visited[i] = false;
		step.pop();
	}
};

const solution = (input) => {
	const n = parseInt(input[0]);

	const visited = Array(n + 1).fill(false);
	const res = [];
	const step = [];
	rec(n, res, step, visited, 0);

	return res.join("\n");
};

console.log(solution(input));