알고리즘 :: 백준 :: Bruteforce :: 10972 :: 다음 순열

문제

문제링크

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

문제접근

• 주어지는 수열의 다음 순열을 구하면 되는 간단한 문제다.
• 이 문제의 존재의의는 <algorithm> 헤더의 next_permutation()을 쓰라는게 아니라 직접 next_permutation()을 구현하라는 문제다.

예를 들어 {1, 2, 3, 4, 5, 6, 7}을 생각해보자.

• 사전 순으로 처음 오는 순열은 1, 2, 3, 4, 5, 6, 7이다. 전체가 오름차순이다.
• 사전 순으로 마지막 순열은 7, 6, 5, 4, 3, 2, 1이다. 전체가 내림차순이다.
• 사전 순으로 두 번째 순열은 1, 2, 3, 4, 5, 7, 6이다.
  눈치챘겠지만, 부분적으로 내림차순이 생긴다!
• 이 인사이트를 시작으로 임의의 순열의 다음 순열을 구하는 방법을 소개한다. 7, 3, 2, 6, 5, 4, 1 이라는 순열을 예로 들어본다.
  1. 뒤에서부터 읽으면서 내림차순이 끝나는 지점을 파악한다.
     • 2 < 6이므로 내림차순이 끝나는 지점이며 여기를 idx라고 표시하겠다. (∴ idx = 3, a[idx] = 6)
  2. idx부터 다시 오른쪽으로 읽으면서 a[idx - 1]보다 크면서 가장 작은 원소를 찾는다. (∴ 4가 2보다 크면서 가장 작음)
  3. 두 수의 위치를 바꾼다. (7, 3, 4, 6, 5, 2, 1)
  4. idx부터 끝까지 부분 배열을 뒤집는다 (7, 3, 4, 1, 2, 5, 6)
• 이처럼 다음 순열을 직접 구현하는 데는 4가지 과정이 소요되며, 크게 무언가를 찾는 과정과 swap하는 과정 두 가지로 나눌 수 있다.
• 알아두자. 외워두자. 써먹자.

코드

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N;
	cin >> N;
	int a[N];
	for (int i = 0; i < N; ++i) cin >> a[i];
	// Step 1. 뒤에서부터 검사하며 내림차순이 끊기는 때를 구한다. 
	int idx = N - 2;	// idx에는 내림차순 시작 직전의 인덱스가 저장.
	for (; idx >= 0; --idx) if (a[idx] < a[idx + 1]) break;
	if (idx < 0) {	cout << "-1\n"; return 0; } // [예외] 마지막 순열
	// Step 2. 내림차순 시작 직전 원소보다 큰 가장 작은 원소를 찾는다.
	int idx2 = N - 1;	// idx2에는 a[idx]보다 크면서 가장 작은 원소 인덱스 저장.
	for (; idx2 > idx; --idx2) if (a[idx] < a[idx2]) break; 
	// Step 3. 두 수의 자리를 바꾼다.
	swap(a[idx], a[idx2]);
	// Step 4. 내림차순 영역을 뒤집는다. 
	for (int i = idx + 1, j = N - 1; i < j; ++i, --j) swap(a[i], a[j]);
	
	for (int i = 0; i < N; ++i) cout << a[i] << ' '; cout << '\n';
}

#include <iostream>
#include <algorithm>
using namespace std;

int N, arr[10000];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> arr[i];
	if (next_permutation(arr, arr + N)) {
		for (int i = 0; i < N; ++i) cout << arr[i] << ' ';
		cout << '\n';
	} else cout << "-1\n";
}

결과