[ 10973 ] [ 순열 ] 이전 순열

문제 설명

---

문제

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

---

풀이 과정

• 이전에 푼 문제중에 다음 순열이라는 문제가 있는데, 해당 문제와 거의 유사하나 몇몇 부분을 바꾸어주어야 하는 부분이 있음.

1. 순열을 오른쪽에서 왼쪽으로 진행하면서 array[i-1]>array[i]인 구간을 찾는다.
   • 이 때, 이러한 구간이 없으면 제일 첫번째 순열인 것이므로 -1을 출력해주면 된다.
   • 구간이 있다면, i-1이 바뀌게 될 요소의 인덱스이다.
2. 다음으로, array[i-1]보다 작은 요소의 인덱스를 오른쪽에서 왼쪽으로 진행하면서 찾는다.
   • 이 요소의 위치를 j라고 두자.
3. array[i-1], array[j]를 서로 바꾸어 준다.
4. 이후, i 이후의 배열들을 뒤집어준다.
   • 내림차순으로 정렬해야 하는데, (1)에서 i를 찾을때, i 이후는 모두 오름차순임을 알 수 있다.
   • 따라서 뒤집어 주면 i 이후는 모두 내림차순이 된다.
5. 배열을 출력해주면 끝

---

소스 코드

import sys

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

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

def prev_permutation(sequence):
    i = len(sequence) - 1

    # sequence[i-1] > sequence[i]인 부분을 찾음 => 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]

    # 바뀌는 점 이후는 내림차순이 되어야 함
    # 위 while문을 보면 알겠지만.. 바뀌는 위치 기준으로 오른쪽은 오름차순이 되어 있음.
    # 따라서, 그냥 뒤집어주면 된다.
    sequence = sequence[:i] + sequence[i:][::-1] 
    return sequence


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