[백준 10973번] 이전 순열 C++ 풀이

단순한 증명 연습하기 좋은 문제가 있어서 포스팅한다

1. 문제

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

10973번: 이전 순열

 

문제를 요약하면 순열이 주어지는데, 주어진 순열보다 사전순으로 바로 앞선 순열을 출력해야한다.

2. 접근

일단 숫자들이 순열이라는 것에 대해서 중복된 숫자가 없고 $1$부터 $N$까지의 숫자임을 알 수 있다.

순열 사전순으로 제시하는 방법에 대해서 생각해보자. $k$번째 자리수가 낮아진다면 더 $k+1$ 번째 자리수들은 본인들이 가지고 있는 자리수들 중 가장 사전순으로 높은 부분순열조합을 가져야한다.

$4\ 3\ 1\ 2\ 5$ 에서 사전순으로 바로 앞선 순열은 $4\ 2\ 5\ 3\ 1$ 으로써 두번째 자리숫자인 $3$이 $2$로 낮아지고 나머지 세번째 자리부터 다섯번째 자리까지 부분순열들은 본인들이 가진 가장 높은 순열 조합인 $ 5\ 3\ 1 $ 을 가지게 된다.

이렇게 구현하면 될거 같다. 그러면 뒤에서부터 각 자리숫자를 탐색하면서 숫자가 높아지는 지점(앞 자리가 숫자가 크다는 것은 앞자리 숫자를 바꾸면 더 작은 순열 조합을 만들 수 있음을 의미한다) 을 찾아 오름차순 정렬하면 가능할 것 같다.

확신이 들지 않는데 증명을 해보자!

 

3. 증명

이 증명은 공부하면서 직접 세워본것이라 논리적 오류이 있을 수 있습니다.

가정: 순열 (중복된 숫자 X, $1$부터 $N$까지의 숫자)

         뒤에서 부터 숫자들을 확인 할 경우 만약 앞의 숫자가 뒤의 숫자보다 크다면 동일한 숫자 구성으로

         사전 순으로 더 낮 은 순열을 만들수 있음이 보장됨 (두 숫자만 바꿔도 더 작은 순열을 만들 수 있음)

명제: 가정에서 말한 앞의 숫자가 뒤의 숫자보다 큰 경우, 해당 숫자를 기준으로 뒤의 숫자 중에 해당 숫자보다 작은 숫자들 중 가장 큰 값과 교환하고(1) 해당 숫자 뒤의 숫자들을 내림차순 정렬하면(2) 사전순으로 바로 앞선 숫자이다.

예를 들어 위와 같은 순열이 주어졌을때, 뒤에 부터 앞자리 숫자가 뒤의 자리 숫자보다 큰 지점을 찾는다

두번째 자리 숫자가 3이고 세번째 자리 숫자가 1이므로 조건에 만족하는 지점을 찾았다.

해당 지점 뒤의 숫자들중에서 두번째 자리 숫자 보다 큰 숫자중 가장 작은 숫자 3을 찾아 바꾼다.(1)

(1)에서 교환한 지점 뒤의 숫자들을 내림차순 정렬한다.(2)

 

이제 증명을 해보자

귀류법을 사용해서 결론을 부정한다.

가정에서 말한 앞의 숫자가 뒤의 숫자보다 큰 경우, 해당 숫자를 기준으로 뒤의 숫자 중에 해당 숫자보다 작은 숫자들 중 가장 큰 값과 교환하고(1) 해당 숫자 뒤의 숫자들을 내림차순 정렬하면(2) 사전순으로 바로 앞선 숫자가 아니다.(아에 사전순으로 뒤인 순열이거나 작은 순열들 중에 바로 앞선 순열가 아닌 더 작은 순열이여야한다)

 

먼저 사전순의 뒤인 순열일 수 없다(변경이 일어나는 가장 앞선 자리수가 (1)에 의해 기존보다 작기 때문에)

그러면 작은 순열이지만 바로 앞선 작은 순열이 아닌 더 작은 더 앞선 순열 일 수 있는가?

 

순열들을 비교할때, 동일한 값들은 볼필요가 없기 때문에 변경된 부분만 봐야한다. 위 그림에서 빨간 숫자와 파란 숫자들이다. 

빨간 숫자들은 (1)에 의해 기존 숫자보다 작아지고, 변경된 숫자는 이 자리숫자에 의해 반드시 바로 앞선 작은 순열이 포함되는 순열 조합이다.(포함되지 않은 경우는 이 숫자보다 큰 숫자가 존재 해야하는데 (1)에 의해 보장된다.)

따라서 파란숫자만 확인하면 되는데 만들어진 파란색 조합은 해당 조합으로 만들수 있는 가장 사전순으로 늦은 숫자이다.(더 사전 순으로 높은 숫자를 만들기 위해서는 더 높은 숫자가 존재해야하는데 이경우 빨간 숫자가 해당 수가 되기 때문에 모순이다. 이미 뒤의 수보다 높은 경우가 발생하기 때문이다.)

따라서 바꿔진 빨간숫자에 의해 바로 앞선 작은 순열이 포함되는 순열 조합이고, 파란숫자에 의해 이 순열은 작은 순열중 가장 사전 순으로 나중의 순열이 되기 때문에 모순이 발생.

귀류법으로 증명

(위 방법 말고 다른 방법이 존재한다는 방식으로 귀류법으로 증명가능)

 

4. 구현

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

int N;
int arr[10001];

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	int index = 0;
	for (int i = N-1; i >= 1; i--) {
		if (arr[i] > arr[i + 1]) {
			index = i;
			break;
		}
	}
	if (index == 0) {
		cout << -1;
		return 0;
	}
	int temp = arr[index];
	int temp_index = index;
	for (int i = index + 1; i <= N; i++) {
		if (arr[i] < arr[index]) {
			temp = arr[i];
			temp_index = i;
		}
	}
	
	swap(arr[index], arr[temp_index]);
	sort(arr + index+1, arr + 1 + N,greater<>());
	for (int i = 1; i <= N; i++) {
		cout << arr[i] << " ";
	}

	return 0;
}

에외 경우를 별도로 처리해 주어야한다.

5. 여담

사실 이문제는 cpp에서 제공하는데 prev_permutation, next_permutation을 사용하여 풀 수 있다..