C++ 백준 10972번

백준 10972번 www.acmicpc.net/problem/10972

10972번: 다음 순열

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

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전 순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

다음에 올 순열을 구하는건데 c++ STL의 algorithm에 이미 next_permutation과 prev_permutation함수가 구현돼있어서 얘네를 쓰면 쉽게 작성할 수 있다. 근데 이거 쓰라고 낸 문제는 아닐 거니까 직접 구현해보자!!

 

먼저 다음 순열에 대해 규칙을 찾아야 된다.

[1,2,3,4,5,6,7] 얘네들로 순열을 만들어보자.

1 2 3 4 7 6 5 다음에는

1 2 3 5 4 6 7 이 온다.

 

1 2 3 5 7 6 4 다음에는

1 2 3 6 4 5 7 이 온다.

 

1 2 7 6 4 5 3 다음에는

1 2 7 6 5 3 4 이 온다.

 

코드로 짜는 거 말고 평소에 우리는 이걸 어떻게 구하냐면

1 2 3 4 7 6 5는 4 다음에 오는 애들은 끝났으니까(사전 순이니까)

4 다음인 5를 4 대신 넣고 그다음 오름차순으로 숫자를 적는다.

그래서 1 2 3 5 4 6 7을 구했다.

 

1 2 3 5 7 6 4도 마찬가지로 5 다음에 오는 애들은 끝났으니까 5 다음인 6을 5 대신 넣고 그다음을 오름차순으로 숫자를 적는다.

그러면 1 2 3 6 4 5 7이 나온다.

 

1 2 7 6 4 5 3 다음을 구하면 4 다음에 오는 애들은 끝났으니까 4 다음인 5를 넣고 4 대신 넣고 그다음을 오름차순으로 적는다.

그러면 1 2 7 6 5 3 4 가 나온다.

 

얘네들을 다시 정리해보자!!

1 2 3 4 7 6 5는 1 2 3 5 4 6 7 , 1 2 3 5 7 6 4는 1 2 3 6 4 5 7, 1 2 7 6 4 5 3은 1 2 7 6 5 3 4

그래서 뭐 어쩌라고 싶을텐데

잘 보면 저기 맨 뒤의 굵은 숫자들이 내림차순에서 오름차순으로 바뀐 걸 알 수 있다.

그리고 이 처음 순열의 내림차순 바로 앞의 숫자가 (1 2 3 4 7 6 5 여기서 4) 뒤에서부터 봤을 때 얘보다 처음으로 큰 수랑 바뀌는 것도 알 수 있다!!!!!!!!!(1 2 3 4 7 6 5 여기 뒤에서부터 4보다 처음으로 큰 5랑 바뀐다!!)

 

1 2 7 6 4 5 3 얘도 마지막 내림차순의 바로 앞인 4가 뒤에서부터 봤을 때 얘보다 처음으로 큰 수 5랑 바뀌고 원래 내림 차순 자리가 오름차순으로 바뀌었다(뒤집혔다).

 

이제 규칙을 찾았으니까 코드로 작성할 수 있다!!!! 

우리가 해야 될 건 맨 뒤의 내림차순인 친구들을 조사하고 그 앞 숫자와 내림차순 친구들 중에 뒤에서부터 봤을 때 이 앞 숫자 친구보다 처음으로 큰 숫자를 찾아서 swap 하고 원래 내림차순 자릿수를 오름차순으로 바꿔주면 된다.

 

그리고 7 6 5 4 3 2 1 이렇게 완전히 내림차순인 애들이 마지막 순열이다.

 

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

bool next_permutation(vector<int> &a, int n) {
	int i = n - 1;
	while (i > 0 && a[i - 1] >= a[i]) i -= 1; // 뒤에서부터 어디까지 내림차순인지 찾아보기
	// while문을 빠져나왔을때의 i가 내림차순의 시작하는 부분
	if (i <= 0) return false; // 마지막 순열
	int j = n - 1;
	while (a[j] <= a[i - 1]) j -= 1; // 내림차순 바로 앞의 숫자보다 처음으로 큰 j를 뒤에서부터 찾아보기
	swap(a[i - 1], a[j]); // 둘 swap
	j = n - 1; // 순열의 마지막 자리
	while (i < j) { // 내림차순의 시작부분부터 마지막 자리까지 뒤집어준다
		swap(a[i], a[j]);
		i += 1;
		j -= 1;
	}
	return true;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (next_permutation(a, n)) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
	}
	else cout << -1 << '\n';

}

STL을 쓰면 진짜 행복하게 풀 수 있다.

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (next_permutation(a.begin(), a.end())) {
		for (int i = 0; i < n; i++) {
			cout << a[i] << ' ';
		}
	}
	else cout << -1;
	cout << '\n';
}