본문 바로가기
알고리즘/[python] 백준 BOJ

[python] 백준 10973 이전 순열

by Alan_Kim 2023. 1. 8.
728x90
반응형

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

 

10973번: 이전 순열

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

www.acmicpc.net

 

문제 해결

10972와 반대 문제

https://thought-process-ing.tistory.com/92

 

[python] 백준 10972 다음 순열

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문

thought-process-ing.tistory.com

 

뒤에서 부터 주어진 순열을 봤을 때 처음으로 i-1번째 수가 i번째 수보다 작을 때 i-1번째 수를 기준으로 잡고 다시 뒤에서부터 순열을 보았을 때 처음으로 i-1번째 수보다 큰 j번째 수(i≤j)를 보고 i-1번째 수와 j번째 수를 바꾸고 i번째 수부터 n번째 수까지 큰 수부터 수를 나열하는 내림차순으로 리스트를 정렬해 이어 붙이면 된다.

(ex) 12543

 5번째 수부터 봤을 때

4>3 이므로 pass,

5>4이므로 pass,

2<5이므로 2를 고정으로 잡고 다시 뒤에 수부터 봤을 때

2<3이므로 2와 3의 수의 위치를 바꾼다. → 13542

13542에서 13 + (542를 내림차순으로 정렬)→ 13542

답 13542

 

CODE

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]:
        for j in range(n-1,0,-1):
            if A[i-1] > A[j]:
                A[i-1], A[j] = A[j], A[i-1]
                B = sorted(A[i:], reverse=True)
                A = A[:i] + B
                print(*A)
                exit()
print(-1)

 

728x90
반응형

댓글