[ 10972 ] [ 순열 ] 다음 순열

문제 설명

---

문제

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을 출력한다.

---

풀이 과정

• 어떻게 구현하는지 모르겠어서.. next_permutation 알고리즘을 찾아 봄

1. 현재 순열을 오른쪽 -> 왼쪽으로 검사하면서 a[i] > a[i-1]인 i점을 찾음.
   • 여기서, i-1번이 바꾸게 될 타겟임.
   • 만약 맨 왼쪽까지 그런 점이 없다면 마지막 순열인 것
2. 다시 현재 순열을 오른쪽 -> 왼쪽으로 검사하면서, 바꾸게 될 타겟보다 큰 값의 위치를 찾음.
   • a[j] > a[i-1]인 점 j를 찾음.
3. a[j]와 a[i-1]을 바꾸어 준다.
4. 마지막으로, i번째 이후의 순열들을 오름차순으로 정렬해주면 된다. (i번째 순열 포함)
   • 이 때, 사실상 i번째 이후의 순열들은 내림차순이므로 거꾸로 붙여주면 됨.
   • 스왑으로 구현하여도 됨. (i <-> 맨 오른쪽), (i-1 <-> 맨 오른쪽-1), ...

---

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())

sequence = list(map(int, sys.stdin.readline().rstrip().split()))

def next_permutation(sequence):
    i = len(sequence) - 1
    # sequence[i-1] < sequence[i]인 경우, sequence[i-1]이 바꾸게 될 타겟
    while i > 0 and sequence[i-1] > sequence[i]:
        i = i - 1

    if i == 0:
        return None

    swap_pos = i-1
    # 바꾸게 될 타겟보다 큰 값의 위치를 찾음
    j = len(sequence) - 1
    while j > 0 and sequence[swap_pos] >= sequence[j]:
        j = j - 1

    # 두 값을 서로 바꾸어 줌
    sequence[swap_pos], sequence[j] = sequence[j], sequence[swap_pos]

    k = len(sequence) - 1
    sequence = sequence[:i] + (sequence[i:])[::-1]        
    return sequence


p = next_permutation(sequence)
if p == None:
    print(-1)
else:
    print(*p)