[백준 10972] 다음 수열

사실 STL을 사용하면 매우 쉽게 풀 수 있는 문제이지만, 직접 구현을 하거나 STL에 구현이 되어 있다는 것을 모르면, 귀찮아지는 문제이다.

배열의 인덱스 가지고 재미있게 코딩할 수 있다는 점이 상당히 놀랍다.

참고하면 좋은 글 : https://redcoder.tistory.com/7

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

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

#include<iostream>
#include<vector>
 
using namespace std;
 
 
bool next_permutation(int *a, int n){
    int i = n-1;                    // 뒤부터 시작 
    while(i > 0 && a[i] <= a[i-1])    // 어디까지가 감소수열인가?? 
        i -= 1;
    if(i <= 0)                        // 전체가 감소수열이다. 
        return false;                // 다음 수열은 존재하지 않는다.
    int j = n-1;
    while(a[i-1] >= a[j])            // i-1보다 작거나 같은 뒤에 있는 수 찾기  
        j -= 1;            
    swap(a[i-1],a[j]);                // 찾은 수의 바로 앞 swap i-1 
    j = n - 1;                        // j는 마지막 
    while(i < j){                    // i-1 이후로, swap해줌 
        swap(a[i],a[j]);
        i +=1;
        j -=1;
    }
    return true;
}
 
int main(){
    int n;
    cin >> n;
    
    int *v = new int[n];
        
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    
    if(next_permutation(v, n)){
        for(int i = 0; i < n; i++)
            cout << v[i] << ' ';
    }
    else{
        cout << "-1";
    }
    
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.