CodeDrive

문제:

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N=3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1,2,3
• 1,3,2
• 2,1,3
• 2,3,1
• 3,1,2
• 3,2,1

입력:

첫째 줄에 N(1<=N<=10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

풀이방법:

C++에서는 next_permutation을 사용하면 쉽게 풀 수 있지만 python에는 이 알고리즘을 구현해서 풀면 된다.

next_permutation은 다음과 같은 알고리즘을 통해서 구한다.

1 4 3 2를 예시로 알고리즘을 알아본다.

1. 뒤에서부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고, (1,4)가 해당된다. 
   1. 이 때, 1의 인덱스를 x라고 칭한다.
   2. 4의 인덱스는 y라고 한다.
2. 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
   1. 1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap한다.
3. y에 해당하는 인덱스부터 sort를 한 뒤에 이어 붙인다.
   1. 4 3 1을 sort해서 1 3 4가 된다.
   2. 이어 붙이기 때문에 2 1 3 4가 된다.

문제링크:

www.acmicpc.net/problem/10972