[백준] 10973번 이전 순열 ★

💡문제접근

• 이전 포스팅에 있었던 next_permutation과 반대인 previous_permutation알고리즘에 대한 문제로 사전순으로 입력으로 주어진 순열의 이전 순열을 구하는 문제다. 다음 순열을 미리 공부했더니 정말 수월하게 접근할 수 있었다.

5 3 4 1 2 5를 예시로 알고리즘을 살펴보자.
①. 뒤에서부터 순열을 비교하며, 앞부분의 값이 뒷부분의 값보다 크다면 조건문을 수행한다. 이전 순열을 구하는 것이기 때문에 앞부분의 값이 뒷부분의 값보다 작아야 하므로 이와 반대인 경우 즉, 앞부분의 값이 뒷부분의 값보다 큰 경우 swap을 수행한다.
②. (2 ＜ 5)(x), (1 ＜ 2)(x), (4 ＞ 1)(o)이므로 4와 1을 swap한다.
③. 기존의 1이 있던 인덱스를 기준으로 그 뒤에 있는 모든 깂들을 내림차순 정렬한다.

💡코드(메모리 : 31760KB, 시간 : 48ms)

import sys

N = int(input())
li = list(map(int, input().split()))

for i in range(N-1, 0, -1):
    if li[i-1] > li[i]:
        for j in range(N-1, 0, -1):
            if li[i-1] > li[j]:
                li[i-1], li[j] = li[j], li[i-1]
                li = li[:i] + sorted(li[i:], reverse=True)
                for i in li:
                    print(i, end = " ")
                sys.exit()
print(-1)

💡소요시간 : 10m