[python] 백준 10972 다음 순열

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

10972번: 다음 순열

 

문제 해결

다음에 오는 순열을 어떻게 표현할 수 있을지 알아내기 쉽지 않다.

순열을 뒤에서 부터 본다. → 순열의 i번째 수와 i-1번째 수와 비교했을 때 i-1번째 수가 i번째 수보다 작을 때

다시 i-1번째 수와 순열의 마지막 수부터 비교를 해서 i-1번째 수와 j번째 수(i-1 ≤ j)가 처음으로 되는 수와 바꾼다.

→ i번째 수까지 그대로 출력하고 i+1번째 수부터는 sorted()를 이용하여 가장 작은 수부터 나열 한다.

만약 한 번도 수를 바꾸지 않았을 때 -1을 출력한다.

 

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]
                A = A[:i] + sorted(A[i:])
                print(*A)
                exit()
print(-1)