백준10972(파이썬) - 다음 순열

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

10972번: 다음 순열

• 처음에는 permutation 으로 n까지의 수 중 나올 수 있는 순서의 경우의 수를 모두 구해서 풀었었는데 당연히 시간초과가 발생했다. N이 20까지인데 시간복잡도가O(N!)이기 때문에 어마어마한 시간이 걸렸다.
• 그래서 생각한건 규칙을 찾았다. 다음 순열문제 규칙은 뒤에서 부터 차례로 탐색하면서 이전 숫자 보다 현재 숫자가 크면 자리를 바꿔주고 바꿔준 숫자 인덱스 뒷부분은 정렬을 해주면 된다.

import sys
input = sys.stdin.readline
#from itertools import permutations

n = int(input())
data = list(map(int,input().split()))
flag = 0
for i in range(n-1,0,-1):
    if data[i-1] < data[i]:
        for j in range(n-1,0,-1):
            if data[i-1] < data[j]:
                data[i-1],data[j] = data[j],data[i-1]
                ans = data[:i]+sorted(data[i:])
                flag = 1
                break
    if flag == 1:
        print(*ans)
        break
else:
    print(-1)
    
# num = [i for i in range(1,n+1)]
# num_permutations = list(permutations(num,n))

# for i in range(len(num_permutations)):
#     if list(num_permutations[i])== data:
#         if i == len(num_permutations)-1:
#             print(-1)
#         else:
#             for i in num_permutations[i+1]:
#                 print(i,end=" ")

##permutations 쓰면 메모리초과, 시간초과