[algorithm] 백준 - 이전 순열

이전 순열

이전 순열은 다음 순열과 비슷한 방식으로 푼다.

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

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

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

1, 3, 2, 4의 이전 순열은
1, 2, 4, 3이 된다.

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

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

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

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

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

자세히 살펴보자면,

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

여기서는 arr[3]을 기준으로 나눈다.

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

arr[3]
3

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

그러면 arr[3]이므로 arr[2]와 swap한다.

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

arr[3]
4

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

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

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

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

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102801.cpp

jeongdaeun98/algorithm