[백준/c++] 10972 다음순열 / 10973 이전순열

문제 10972

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

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

구현해야할 조건

next_permutation의 반환값이 boolean인것을 문제를 해결하면서 배웠다.

code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;

int main(void){


	cin >> N;

	vector<int> v(N);

	for(int i=0;i<N;i++)
		cin >> v[i];

	bool flag = next_permutation(v.begin(), v.end()); 

	if(!flag) 
	{
		cout << -1; 
		return 0;
	} 

	for(int i=0;i<N;i++)
		cout << v[i] << ' ';

	return 0;

}

 

문제 10973

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

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

구현해야할 조건

prev_permutation으로 구하는 문제, 위 문제와 유사하다. 

code

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;

int main(void){


	cin >> N;

	vector<int> v(N);

	for(int i=0;i<N;i++)
		cin >> v[i];
		
	bool flag = prev_permutation(v.begin(), v.end()); 

	if(!flag) 
	{
		cout << -1; 
		return 0;
	} 

	for(int i=0;i<N;i++)
		cout << v[i] << ' ';

	return 0;

}