[algorithm] 백준 - 다음 순열

순열을 나열했을 때 주어진 순열 다음 순열을 출력하는 문제이다.

1, 2, 3을 예시로 들어본다면,
다음 순열은 1, 3, 2가 된다.

1, 2, 3, 4를 예시로 들어본다면,
다음 순열은 1, 2, 4, 3이 된다.

1, 2, 4, 3의 다음 순열은
1, 3, 2, 4가 된다.

4, 3, 2, 1의 다음 순열은 없으므로 -1을 출력한다.

다음 순열이 존재할 수 있는 조건은 arr[i - 1] < arr[i]가 존재해야한다.

뒤에서 앞으로 반복문을 수행 후, 이 조건에 만족하는 수를 기준으로 양쪽으로 나눈다.

이후 arr[i - 1]보다 큰 수를 arr[i] 쪽 순열을 뒤에서 앞으로 조회 후 swap한다.

그 후 arr[i] 쪽 순열을 오름차순 sort하면 다음 순열이다.

자세히 살펴보자면,

arr[0]	arr[1]	arr[2]	arr[2]
1	2	4	3

여기서는 arr[2]를 기준으로 나눈다.

arr[0]	arr[1]
1	2

arr[2]	arr[3]
4	3

(i = 2) arr[1] 보다 큰 수를 arr[2] 수열에서 뒤에서 앞으로 조회 후 swap한다.

그러면 arr[3]이므로 arr[1]과 swap한다.

arr[0]	arr[1]
1	3

arr[2]	arr[3]
4	2

그 후 arr[2] 수열을 오름차순으로 sort한다.

arr[0]	arr[1]	arr[2]	arr[3]
1	3	2	4

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

vector<int> beforeAnswerVector;
void swap(int i, int j){
    int temp = beforeAnswerVector[i];
    beforeAnswerVector[i] = beforeAnswerVector[j];
    beforeAnswerVector[j] = temp;
}
int main(void){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;
        beforeAnswerVector.push_back(num);
    }
    bool isNext = false;
    for(int i = n - 1; i > 0; i--){
        if(beforeAnswerVector[i - 1] < beforeAnswerVector[i]){
            isNext = true;
            for(int j = n - 1; j >= i; j--){
                if(beforeAnswerVector[i - 1] < beforeAnswerVector[j]){
                    swap(i - 1, j);
                    break;
                }
            }
            sort(beforeAnswerVector.begin() + i, beforeAnswerVector.end());
            break;
        }
    }
    if(!isNext) cout << -1;
    else{
        for(int i = 0; i < n; i++){
            cout << beforeAnswerVector[i] << " ";
        }
    }
}

github.com/jeongdaeun98/algorithm/blob/master/2020/20102706.cpp

jeongdaeun98/algorithm