문제

사전순으로 나열했을 때 다음에 오는 순열을 구하는 문제. algorithm 헤더의 next_permutation을 쓰면 된다.

직접 구현하려면

  1. v[i-1] < v[i]를 만족하는 가장 큰 i를 찾는다.
  2. j >= i이면서 v[j] > v[i-1]를 만족하는 가장 큰 j를 찾는다.
  3. v[i-1]와 v[j]를 swap한다.
  4. v[i]부터 끝까지 배열을 뒤집는다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int N;

bool go() {
	int i, j;

	i = N - 1;
	while (i && v[i - 1] >= v[i]) i--;
	if (i <= 0) return false;

	j = N - 1;
	while (v[j] <= v[i - 1]) j--;
	swap(v[i - 1], v[j]);

	j = N - 1;
	while (i < j) {
		swap(v[i], v[j]);
		i++; j--;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int i, tmp;
	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	if (go()) {
		for (i = 0; i < N; i++) cout << v[i] << " ";
	}
	else cout << "-1";
	cout << endl;

	return 0;
}