백준 10973번 이전 순열

문제 링크입니다: https://www.acmicpc.net/problem/10973

prev_permutation을 사용하면 간단히 풀 수 있는 문제였지만 직접 구현해봤습니다.

알고리즘은 아래와 같습니다.

1. v[idx - 1] > v[idx]를 만족하는 가장 큰 idx를 찾습니다.

2. idx2 >= idx이면서 v[idx2] < v[idx2-1]을 만족하는 가장 큰 idx2를 찾습니다.

3. v[idx - 1]과 v[idx2]를 뒤바꿔줍니다.

4. idx부터 순열을 뒤집어줍니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

vector<int> v;

 

int main(void)

{

        cin >> N;

 

        v.resize(N);

        for (int i = 0; i < N; i++)

                 cin >> v[i];

 

        int idx = N - 1;

        //v[idx - 1] > v[idx]를 만족하는 가장 큰 idx를 찾는다

        while (idx > 0 && v[idx - 1] <= v[idx])

                 idx--;

        //첫 번째 순열

        if (idx == 0)

        {

                 cout << -1 << "\n";

                 return 0;

        }

 

        int idx2 = N - 1;

        //idx2 >= idx이면서 v[idx2] > v[idx2-1]을 만족하는 가장 큰 idx2를 찾는다

        while (v[idx - 1] <= v[idx2])

                 idx2--;

 

        swap(v[idx - 1], v[idx2]);

        idx2 = N - 1;

        //v[idx]부터 순열을 뒤집는다

        while (idx < idx2)

        {

                 swap(v[idx], v[idx2]);

                 idx++;

                 idx2--;

        }

 

        for (int i = 0; i < N; i++)

                 cout << v[i] << " ";

        cout << "\n";

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~