[python] 백준 10972번 다음 순열

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

10972번: 다음 순열

 

---

 

💻 코드

 

import sys

input = sys.stdin.readline

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

for i in range(n - 1, 0, -1): # 뒤에서부터 탐색
    if array[i - 1] < array[i]: # 앞의 숫자가 뒤의 숫자보다 더 크면
        for j in range(n - 1, 0, -1): # 뒤에서부터 탐색
            if array[i - 1] < array[j]: # 해당 값(i-1)보다 뒤에 있는 값(j)이 더 크면
                array[i - 1], array[j] = array[j], array[i - 1] # swap
                array = array[:i] + sorted(array[i:]) # i를 기준으로 뒤에는 정렬하고 합치기
                print(*array)
                exit()
print(-1)

 

 

 

 

 

📝 풀이

 

이 문제는 파이썬의 itertools 모듈에 있는 permutation을 이용하려고 하면 시간 초과가 발생한다. 따라서 위와 같은 알고리즘을 통해서 풀어야 한다.

 

 

 

예시

 

n = 4, array = [1, 3, 4, 2] 일때

 

뒤에 있는 인덱스부터 탐색한다.

 

i = 3일 때

if array[i-1] < array[i]

array[2] > array[3]은 성립하지 않고

 

i = 2일 때

array[1] < array[2]은 성립하므로

j를 뒤에 있는 인덱스부터 탐색하여 array[i-1] 값보다 큰 값을 찾는다.

 

if array[i-1] < array[j]

 

j = 3일 때

array[1] > array[3]은 성립하지 않고

 

j = 2일 때

array[1] < array[2]은 성립하므로

그 두 값을 swap한다.

 

array[i]를 기준으로 앞의 값은 그대로 뒤의 값은 정렬한 후 합친다.

출력을 하고 코드 종료시킨다.

 

코드 종료가 되지 않을 경우에는(마지막 순열이면) -1을 출력하도록 한다.