BOJ 10972 다음 순열

 

문제 링크 : https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

가장 마지막에 오는 것은 내림차순이라는 문제의 설명이 모든 것을 말해 주고 있다.

 

N=5 인 경우 즉, 1 2 3 4 5 로 이루어지는 한 순열을 관찰해 보자.

$$23541$$

 

1. 순열에서 가장 긴 내림차순으로 이루어진 마지막 부분(suffix)을 찾았을 때, 

앞 부분이 2  3 으로 시작되는 순열의 마지막임을 알게 된다.

그렇다면 앞 부분 2  3 을 바꾸어야 할 것이다.

 

2. 뒤의 5  4  1 중에서 3 보다 큰 첫 수를 찾아서 바꾸어야 한다.

 

3. 2의 결과 앞 부분은 2  3 에서 2  4 로 바뀌고 뒷 부분은 1  3  5 로 두고 새로이 순열을 구성한다.

 

위의 1, 2, 3 단계를 일반화시키면 문제는 해결된다.

 

	#include<bits/stdc++.h>
	using namespace std;
	int N, arr[10001];
	int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++) scanf("%d",&arr[i]);
	// 1. 가장 긴 내림차순 suffix 를 찾는다.
	int a=-1;
	for(int i=N-1;i>0;i--)
	if(arr[i-1]<arr[i]){
	a=i-1;
	break;
	}
	if(a==-1) {
	printf("-1\n");
	return 0;
	}
	// 2. 앞 부분의 마지막 수와 바꿀 내림차순 suffix 내부의 수를 찾는다.
	int b=N-1;
	while(arr[a]>arr[b])
	b--;
	swap(arr[a],arr[b]); // 3. 두 수를 교체한다.
	vector<int> res;
	for(int i=0;i<=a;i++) res.push_back(arr[i]);
	for(int i=N-1;i>a;i--) res.push_back(arr[i]); // 4. 뒷 부분을 오름차순으로
	for(int i=0;i<N;i++)
	printf("%d ", res[i]);
	printf("\n");
	}

view raw boj10972.cpp hosted with ❤ by GitHub