[알고리즘/백준] 10972번 : 다음 순열(python)

permutation으로 풀면 시간초과가 난다. O(N!)임...

규칙을 찾아야 한다.

예를 들면
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
이라고 하면
제일 오른쪽부터 시작한다. 만약 지금 수가 그 다음 수보다 크면 인덱스를 저장하고...다시 for문을 돌린다

3 2 4 1이면
1이 4보다 작다 -> 4가 2보다 크다 -> 4와 2의 인덱스를 가지고 다시 for문을 돌린다. -> 만약 2보다 큰게 나오면 해당 수와 자리를 바꿔준다. -> 2의 인덱스 뒤는 sort 해준다.

N = int(input())
a = list(map(int, input().split()))

for i in range(N-1, 0, -1):
    if a[i] > a[i-1]:
        x, y = i-1, i
        for j in range(N-1, 0, -1):
            if a[j] > a[x]:
                a[j], a[x] = a[x], a[j]
                a = a[:i] + sorted(a[i:])
                print(*a)
                exit(0)
print(-1)