[ 백준 10972 , 10973 ] 다음 순열 , 이전 순열 (C++)

백준의 다음순열, 이전순열 (10972, 10973) 문제이다.

[ 다음순열(10972) 문제 바로가기 ]

[ 이전순열(10973) 문제 바로가기 ]

[ 다음순열(10972) / 이전순열(10973) 문제풀이 ]

1) 사실, 본인은 순열을 구하는데 있어서 STL에서 제공해주는 permutation() 함수를 사용하는 것을 별로 좋아하진 않는다.

   그래서, 처음에는 모든 순열을 구해보고, 정답 조건에 맞는 순열을 출력하는 식으로 구현하였는데 시간초과가 발생하였다.

   시간초과를 해결할 방법을 모르겠어서, 많은 사람들의 코드를 참고해봤지만 생각보다 쉽게 이해가 되지 않았다.

   그래서, 이 문제에서는 next_permutation() 함수를 사용하였다.

   next_permutation()이라는 함수는 헤더파일 "#include<algorithm>"을 선언하면 사용할 수 있는 순열을 구현해주는 함수이다.

   그래서, 이 함수를 통해서 while문으로 순열을 모두 구현하는 방법도 있긴 있다.

   next_permutation()으로 순열을 구현하는 방법은 간략하게 이렇다. 함수 이름처럼, 이 다음에 나올 수 있는 순열이 존재한다면,

   순열을 출력한다 이런 느낌이다. 즉, while문으로 이 다음에 나올 수 있는 순열이 없을 때 까지 반복시키면서, 순열을 구해주는

   함수이다.

   이 문제에서는, 이놈이 굉장히 유용하게 사용된다.

   '다음순열'의 문제는, 문제에서 주어진 순열 다음에 나올 순열을 출력하는 것이다.

   즉, if(next_permutation(Arr, Arr + N) == true) 이 조건문만 써주면 문제가 해결된다.

   next_permutation뒤에 매개변수로 오는 것은, 순열을 나타낸다. Arr , Arr + N이면, 우리가 입력받은 순열 값들이 들어갈 것이고,

   저 순열 다음에 올 수 있는 순열이 존재하면 출력한다는 의미이다.

  

   반대로 '이전순열'에도 비슷한 놈이 하나 있다. 바로 prev_permutation()이다. 돌아가는 방식은 위에서 설명한 next_permutation과

   비슷한데, 이름 그대로 '이전에 올 수 있는 순열' 로 개념이 반대일 뿐이다.

   소스코드를 본다면 쉽게 이해하고 알 수 있을 것이다.

  

   참고로, 순열과 조합을 재귀를 통한 구현에 대해서 알고싶으시면 아래의 글을 참고하도록 하자.

   [ 조합 구현하기]

   [ 순열 구현하기 ]

   [ 중복조합 구현하기 ]

   [ 중복순열 구현하기 ]

[ 다음순열(10972) 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 10000
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    if (next_permutation(Arr, Arr + N) == true)
    {
        for (int i = 0; i < N; i++)
        {
            cout << Arr[i] << " ";
        }
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 이전순열(10973) 소스코드 ]

#include<iostream>
#include<algorithm>
 
#define endl "\n"
#define MAX 10000
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    if (prev_permutation(Arr, Arr + N) == true)
    {
        for (int i = 0; i < N; i++)
        {
            cout << Arr[i] << " ";
        }
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}