[C++] next_permutation, prev_permutation

next_permutation, prev_permutation

함수에 벡터의 iterator나 배열의 주소를 넣으면 다음 순열(next_permutation) 또는 이전 순열(prev_permutation)의 결과가 벡터나 배열에 적용된다. 만약 다음 또는 이전 순열이 없다면 False를 return 한다.

 

문제

 

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

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

int num[10000];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> num[i];

	if (next_permutation(num, num + n))
		for (int i = 0; i < n; ++i)
			cout << num[i] << " ";
	else
		cout << -1;
}

 

https://www.acmicpc.net/problem/10973

10973번: 이전 순열

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

int num[10000];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> num[i];

	if (prev_permutation(num, num + n))
		for (int i = 0; i < n; ++i)
			cout << num[i] << " ";
	else
		cout << -1;
}

 

https://leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

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

class Solution {
public:
    void nextPermutation(vector<int>& nums)
    {
        // 참고로, 제공하는 알고리즘이 있다.
        //next_permutation(nums.begin(), nums.end());

        // 뒤에서부터 정렬이 깨지는 인덱스 찾기
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
            --i;

        if (i == -1) {
            reverse(nums.begin(), nums.end());
        }
        else {
            // 정렬이 깨지는 인덱스 교환
            int j = i + 1;
            while (j < nums.size() && nums[i] < nums[j])
                j++;
            swap(nums[i], nums[j - 1]);
            reverse(nums.begin() + i + 1, nums.end());
        }
    }
};