다음 순열

문제

백준 10972번 - 다음 순열

언어

JavaScript

순열이란?

임의의 수열을 다른 순서로 섞는 연산을 말합니다.
크기가 N인 수열의 서로 다른 순열은 총 N! 개 있습니다.
보통 모든 순서를 다 시도해봐야 하는 BruteForce 문제에 사용됩니다.
- 모든 순서를 다 시도해볼 때는 첫 순열과 마지막 순열을 찾고, 첫 순열 부터 다음 순열을 구하는 방식을 통해서 가능합니다.
아래의 두 문장이 순열과 관련해서 가장 중요한 말입니다.
- 모든 순열은 앞에 어떤 수로 시작하는 마지막 순열입니다. 그것의 다음 순열은 앞에 어떤 수로 시작하는 첫 순열입니다.
- 첫 순열은 같은 수가 없으면 오름차순, 같은 수가 있으면 비내림차순입니다. 마지막 순열은 내림차순을 의미합니다.
두 문장을 합해서 결론을 내면,
- 어떤 순열이 앞에 어떤 값으로 시작하는 마지막 순열인지 구합니다.
- 이제 그것의 다음 순열은 앞의 어떤 값의 제일 마지막만 달라지는 첫 순열입니다.

문제 풀이 step 1

위의 결론을 이용해서 다음 순열을 구합니다.
예를 들어,
- 612543 은 612 로 시작하는 마지막 순열입니다. 즉, 어떤 값은 612 입니다.
- 그렇다면 612 의 제일 마지막 즉 2 만 달라지는 첫 순열이 다음 순열입니다. 즉, 61? 로 시작하는 첫 순열을 의미합니다.
- ? 자리에는 뒤에 있는 수 중에서 2 보다 크면서 가장 작은 수를 찾아야 합니다. 즉, 2 보다 바로 한 단계 더 큰 수를 찾아야 하는 것입니다.
- 그리고 찾은 그 큰 수를 ? 자리의 수와 교환합니다.
- 그리고 ? 자리 다음의 수들을 다 오름차순으로 변경하면 첫 순열이 됩니다. 위 과정을 수행하면 ? 자리 다음의 수들이 내림차순의 형태이므로 뒤집기만 해주면 됩니다.

문제 풀이 step 2

위의 과정을 정리해서 순서도로 만들면 아래와 같습니다.
1. A[i - 1] < A[i] 를 만족하는 가장 큰 i 를 찾습니다. (어떤 수의 ? 자리 찾기, ? 는 i - 1 에 위치하게 됩니다.)
2. j >= i 이면서 A[j] > A[j - 1] 를 만족하는 가장 큰 j 를 찾는다. (? 보다 바로 한 단계 더 큰 수 찾기)
3. A[i - 1] 과 A[j] 를 SWAP 한다.
4. A[i] 부터 순열을 뒤집는다. (? 자리 다음의 수들을 오름차순 형태로 변경)
이렇게 다음 순열을 구하는 알고리즘의 시간 복잡도는 O(N) 이고, 모든 순열을 구하는 시간 복잡도는 O(N * N!) 입니다.
추가적으로 1 번 과정에서 boolean 값을 return 하도록 해서 마지막 순열인지 판단하는 로직을 구현합니다.

소스 코드 1

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

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = input[1].split(" ").map(Number);

	// ? 찾기
	let i = n - 1;
	for (i = n - 1; i > 0; i--) {
		if (arr[i - 1] > arr[i]) continue;

		break;
	}

	// 마지막 순열인 경우
	if (!i) return -1;

	// ? 보다 한 단계 큰 수 찾기
	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;
	}

	return arr.join(" ");
};

console.log(solution(input));