[백준] 10972번 : 다음 순열 (C++)

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>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    vector<int> vec;
    int num;
 
    // vector에 해당 순열을 삽입해준다.
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        vec.push_back(num);
    }
 
    // 마지막으로 오는 순열인지 체크하기 위함
    bool flag = 0;
 
    for (int i = n - 1; i > 0; i--)
    {
        // 만약 [i - 1]가 vec[i]보다 작다면,
        // 해당 지점이 다음 순열을 위한 체크포인트가 됨
        if (vec[i - 1] < vec[i])
        {
            for (int j = n - 1; j >= i; j--)
            {
                // 다시 순열의 맨 뒤부터 [i - 1]보다 큰 수를 찾고
                // 해당 수를 스왑해준다.
                if (vec[i - 1] < vec[j])
                {
                    swap(vec[i - 1], vec[j]);
                    break;
                }
            }
            
            // 스왑한 뒷 수부터 정렬을 해주면 다음 순열이 됨.
            sort(vec.begin() + i, vec.end());
            flag = 1;
            break;
 
        }
    }
 
    if (flag)
    {
        for (auto& ele : vec)
        {
            cout << ele << " ";
        }
    }
    else
    {
        cout << "-1";
    }
 
    return 0;
}
 

---

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

10972번: 다음 순열