[백준-10973] 이전 수열 / Python

10973번: 이전 순열

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

k = -1
for i in range(len(arr) - 1):
    if arr[i] > arr[i + 1]:
        k = i

if k == -1:
    print(-1)
else:
    for i in range(k + 1, len(arr)):
        if arr[i] < arr[k]:
            m = i

    arr[k], arr[m] = arr[m], arr[k]

    temp = arr[k + 1 :]
    temp.sort(reverse=True)
    answer = arr[: k + 1] + temp

    for num in answer:
        print(num, end=" ")

 

해설

a[k] > a[k+1]이 성립하는 k의 최대를 찾는다.

k가 -1이면 이미 오름차순이 되어있다는 뜻이다.

 

인덱스 k 이후의 값들 중 a[k] > a[m]이 성립하는 m의 최대를 찾는다.

 

k와 m 자리의 값을 서로 바꿔준다.

 

인덱스 k 이후의 값들을 내림차순으로 정렬한다.