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

문제링크

https://www.acmicpc.net/problem/10973

10973번: 이전 순열

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().split()))
 
for i in range(n-1, 0, -1):
    if a[i-1]>a[i]:
        target = i-1
        break
else:
    print(-1)
    sys.exit()
    
for i in range(n-1, 0,-1):
    if a[i]<a[target]:
        a[i], a[target] = a[target],a[i]
        break
a = a[:target+1] + sorted(a[target+1:], reverse = True)
print(*a)
 
 

 

POINT

다음 순열 문제와 반대로 접근해서 풀면된다.

-https://rrojin.tistory.com/46

[백준] 10972 다음 순열 파이썬 python

 

예를 들어, [5, 3, 1, 2, 4] 이전 순열을 만들고자 한다. 

 

Step1.

 더 작은 순열을 만들어야하기에 큰 수가 앞에 배치된 게 있는지 확인해야한다. '1,2,4'는 오름차순으로 배치되어있으니 1,2,4의 조합으로는 더이상 작은 수를 만들 수 없기에 건드릴 필요가 없다. 3>1이므로 Target은 숫자 3!! (==>코드 구현상에서는 Target = 3의 index 1) 

 

Step2.

 3 이후로는 오름차순으로 배치되어있는것이기 때문에 '1,2,4'를 뒤에서 부터 접근해서 3과 비교해본다. 3보다 더 작은 수가 앞으로 튀어나올 자격이 있다. 3<4이므로 넘어가고, 3>2이기 때문에 3과 2의 자리를 바꿔서 2를 앞으로 보낸다.

여기까지하면, [5,3,1,2,4] -> [5,2,1,3,4]가 된다.

 

Step3.

자 이제, [5,2]로 시작하는 제일 마지막 순열을 구해야하기 떄문에 그 뒤는 '1,3,4'로 만들 수 있는 제일 큰 순열을 갖추어야한다. 따라서 sorted(reverse=True)를 통해 내림차순 배열을 한다. 

[5,2] + 내림차순([1,3,4]) =>> [5,2,4,3,1] 완성!!!!