[백준][파이썬] 10973 이전순열

[핵심]

다음 순열과 원리가 반대이다

1. 왼쪽이 큰경우를 찾아주기

2. 그 수 보다 오른쪽에 있는 그 보다 작은 수 찾기

3. 두 개의 숫자 바꾸고 오름차순 정렬

*오름차순 정렬을 할때 이중포문을 해서 하면 시간초과가 난다. 대신 순열 특성상 이미 내림차순이 되어있다는 점을 활용하여 while문으로 뒤집어주면 된다.

사실 위에 말한 내용을 이해하려고 하면 쉽지 않을것이다. 로직을 스스로 작성하면서 봐야지 이해가 쉽다.

num = int(input())
lit = list(map(int,input().split()))

def recu(lit):
    n = len(lit) -1
    i = n-1
    while lit[i] <= lit[i+1]:
        i -= 1
    if i == -1:
        return True
    j = n

    while lit[i] <= lit[j]:
        j -= 1
    lit[i],lit[j] = lit[j],lit[i] #바꿔주기
    while i+1 < n:
        lit[i+1],lit[n] = lit[n],lit[i+1]
        i +=1
        n -=1

    return False

if recu(lit) == True:
    print(-1)
else:
    print(*lit)