[C++] 백준 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;
}
Author And Source
이 문제에 관하여([C++] 백준 10972번 다음 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beclever/C-백준-10972번-다음-순열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)