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)
smilegate