[C++] 백준 15649번 : 다음 순열

10972번: 다음 순열

---

문제

---

풀이

방법 1.

사전 순으로 나열하였을 때 다음 순열을 찾는 문제이다.

순열은 오름차순으로 이루어져 있고 가장 마지막 순열만 내림차순으로 이루어져 있다.

즉, 중복 X

 

만약 순열 A = 8457631 이 845로 시작하는 마지막 순열로 주어졌을 때 다음 순열을 찾는 방법은

 

1.

8   4   5   7   6   3   1

             <   >   >   >

위와 같이 뒤에서부터 시작해 A[i - 1] < A[i] 가 되는 i를 찾는다.

 

2.

다음 순열은 84?으로 시작하므로 이전인 ?는 5보다 크면서 7631중에 가장 작은 수(A[j])를 찾아 주어야 한다.

즉, 7 6 3 1 에서 5보다 크면서 가장 작은 수 A[j] = 6 이 된다.

 

3.

A[i - 1]과 A[j]의 위치를 바꾸어 준다.

8   4   5   7   6   3   1  →  8   4   6   7   5   3   1

 

4.

7531은 첫 순열이 아닌 수 이므로 이 부분을 뒤집어주면 원하는 다음 순열을 구할 수 있다.

8   4   6   7   5   3   1  →  8   4   6   1   3   5   7

 

즉, 순열 A = 8457631 의 다음 순열은 8461357 이 된다.

 

 

방법 2.

C++ algorithm 헤더파일에 포함되어있는 next_permutation함수를 이용하면 아주 간단하게 풀수있다.

---

문제점

처음 디버깅을 했을 때 위의 방식대로 코딩을 했는데도 원하는 결과가 안 나왔다.

원인을 조사해보니 다음 순열을 찾을 때 n - 1이 i 로 들어가게 함수를 만들었으면서 정작 배열 a에 값을 입력받을 때 n까지 입력을 받게 하여 결국 엉뚱한 값이 결과로 나오게 된 것이었다.

 

위의 문제를 해결했는데도 문제가 또 발생하여 원인을 조사하였고 j를 사용하고 난 후 다시 값을 초기화해서 사용을 해야 하는데 초기화를 하지 않아 엉뚱한 인덱스부터 숫자를 뒤집었던 것이었다. 

 

배열을 사용할 때 인덱스를 꼭 주의하자...

---

코드

방법 1.

#include <iostream>
#include <vector>
using namespace std;

bool next_permutation(int *a, int n)
{
    // 애초에 n - 1이 i 로 들어가므로 배열의 인덱스를 주의할 것
    int i = n - 1;
    while (i > 0 && a[i - 1] >= a[i])
    {
        i -= 1;
    }
    if (i <= 0)
    {
        return false;
    }
    int j = n - 1;
    while (a[j] <= a[i - 1])
    {
        j -= 1;
    }
    swap(a[i - 1], a[j]); // 어차피 a[i - 1]보다 크면서 제일 작은 수 임
    j = n - 1; // 꼭 초기화 잊지 말 것
    while (i < j)
    {
        swap(a[i], a[j]);
        i += 1;
        j -= 1;
    }
    return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int n;
    int a[10000];
    cin >> n;

    // 배열의 인덱스 주의
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    if (next_permutation(a, n))
    {
        // 배열의 인덱스 주의
        for (int i = 0; i < n; ++i)
        {
            cout << a[i] << " ";
        }
    }
    else
    {
        cout << "-1";
    }
    
    cout << "\n";

}

 

방법 2.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int n;
    int a[10000];
    cin >> n;

    // 배열의 인덱스 주의
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    if (next_permutation(a, a + n))
    {
        // 배열의 인덱스 주의
        for (int i = 0; i < n; ++i)
        {
            cout << a[i] << " ";
        }
    }
    else
    {
        cout << "-1";
    }
    
    cout << "\n";

}

---

결과

방법 1. : 아래

방법 2. : 위

---

pyo7410/Study