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

문제 링크

10972번: 다음 순열

 

풀이 ) 구현

  이 문제의 경우 풀이 방법을 몰라서 인터넷 검색을 통해서 풀 수 있었다.

https://en.cppreference.com/w/cpp/algorithm/next_permutation

std::next_permutation - cppreference.com

 

1. 먼저 배열의 뒤부터 두 개씩 비교하여 앞의 숫자가 더 작은 경우가 있는지 확인한다.

  5 4 3 2 1 같이 내림차순으로 정렬된 숫자의 경우 모두 앞의 숫자가 크기 때문에 다음 순열이 존재하지 않아 -1을 출력하고 종료한다.

 

2. 앞부분의 숫자가 더 작은 부분을 경계로 해서 뒷부분의 숫자 중 앞의 경계 값보다 큰 값을 찾는다.

  3 2 5 4 1의 경우 3 2 | 5 4 1로 나뉘고 뒷부분의 숫자를 뒤부터 앞의 경계 값인 2와 비교한다.

  2 > 1 -> 2 < 4 : break

 

3. 위에서의 두 값 2와 4의 자리를 바꿔준 다음 뒷부분을 오름차순으로 정렬해준다.

  3 2 | 5 4 1 -> 3 4 | 5 2 1 -> 3 4 | 1 2 5

 

#include <cstdio>
#include <algorithm>	// swap()
using namespace std;

int arr[10001];

int main(void)
{
    int n, i;
    scanf("%d", &n);

    for(i = 0; i < n; ++i)
        scanf("%d", arr+i);

    if(n == 1){
        printf("-1\n");
        return 0;
    }
// 1 start
    for(i = n-1; i > 0; --i)
        if(arr[i-1] < arr[i])
            break;
    if(i == 0)
        printf("-1\n");
// 1 end
// 2 start
    else{
        int j = n-1;
        while(arr[i-1] > arr[j])
            j--;
// 2 end
// 3 start
        swap(arr[i-1], arr[j]);

        sort(arr+i, arr+n);
// 3 end
        for(int k = 0; k < n; ++k)
            printf("%d ", arr[k]);
    }
    return 0;
}

 

※ algorithm 라이브러리의 next_permutation()를 사용하면 더 간단하게 구현할 수 있다.

 

주의점 )

- 처음 답을 제출할 때 99%에서 틀렸다고 나왔는데 첫 번째 if문에서 처리한 길이가 1인 입력에 대한 예외처리를 해주지 못했기 때문이었다.