[C++] 백준 10972번 다음 순열

문제 링크

10972번: 다음 순열

문제 요약

10,000개 이하의 수로 이루어진 수의 순열이 주어질 때, 사전 순으로 다음에 오게 될 순열을 구해야 한다.

접근 방법

문제의 이름에서 알 수 있듯이 std::next_permutation을 이용하면 간단하게 풀 수 있습니다.

template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

std::next_permutation의 C++ 레퍼런스를 참조하면 위와 같습니다.

If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false.

레퍼런스에 쓰여 있듯이 만약에 다음 순열을 찾을 수 없다면 std::next_permutation은 요소들을 첫 번째 순열로 재배열(오름차순)하고, false를 반환하게 됩니다. 따라서 이 문제에서 std::next_permutation이 false를 반환하는 경우에는 -1을 출력해주고, 그 외의 경우에는 원소들을 순서대로 출력해주면 됩니다.

물론 직접 next_permutation을 구현하는 풀이 역시 어렵지 않게 생각해낼 수도 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

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

	if (!next_permutation(v.begin(), v.end()))
		cout << -1;
	else
		for (auto& i : v)
			cout << i << ' ';
	return 0;
}