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

문제

10972번: 다음 순열

풀이

수학

 

N이 최대 10,000이므로 모든 순열을 구한다면 시간 초과에 메모리 초과이다. 주어진 순열의 바로 다음 순열을 구하는 방법은 다음과 같다. 

• 순열의 가장 오른쪽부터 바로 왼쪽 원소가 자신보다 작은지 검사한다. 
• 작다면 그 왼쪽 원소(기준)의 오른쪽 원소들 중 기준보다 큰 값 중 가장 작은 값을 가지는 인덱스를 찾는다. 
• 인덱스와 기준의 원소를 맞바꾼다.
• 기준의 오른쪽 원소들을 오름차순으로 정렬한다. 

만약 첫단계에서 알고리즘이 종료된 경우, 해당 순열은 사전순으로 마지막에 오는 순열인 경우로 -1을 출력한다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    vector<int> nums(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
    }

    bool flag = false;

    // 순열의 가장 오른쪽부터 바로 왼쪽 원소가 자신보다 작은지 검사한다.
    for (int i = N - 1; i > 0; --i)
    {
        // 작다면 i - 1 원소의 오른쪽의 원소들 중 i - 1 원소보다 큰 값 중 가장 작은 값을 가지는 인덱스를 찾는다.
        if (nums[i - 1] < nums[i])
        {
            int index = i;

            for (int j = i; j < N; ++j)
            {
                if (nums[i - 1] < nums[j] && nums[index] > nums[j])
                {
                    index = j;
                }
            }

            // index와 i - 1의 원소를 swap
            swap(nums[i - 1], nums[index]);

            // i - 1의 오른쪽을 오름차순으로 정렬한다.
            sort(nums.begin() + i, nums.end());

            flag = true;

            break;
        }
    }

    if (flag)
    {
        for (int i = 0; i < N; ++i)
        {
            cout << nums[i] << " ";
        }
    }
    else
    {
        // 순열의 마지막 값인 경우 -1을 출력
        cout << "-1";
    }

    return 0;
}