[백준(python)] 10972번: 다음 순열

10972번: 다음 순열

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

풀이 (시간초과)

import sys
from itertools import permutations

num = int(sys.stdin.readline())
data = [i for i in range(1, num+1)]
inputPermu = list(map(int, input().split()))

flag = 0
for per in permutations(data, num):
    if flag == 1:
        for i in per:
            print(i, end=" ")
        exit()
    if list(per) == inputPermu:
        flag = 1
print("-1")

설명

itertools 이용.. 시간초과

맞는 풀이

num = int(input())
data = list(map(int, input().split()))

for i in range(num - 1, 0, -1):
    if data[i - 1] < data[i]:
        for j in range(num - 1, 0, -1):
            if data[i - 1] < data[j]:
                data[i - 1], data[j] = data[j], data[i - 1]
                data = data[:i] + sorted(data[i:])
                print(*data)
                exit()

print(-1)

설명

n이 5일때
5 3 2 4 1 의 다음 순열은 5 3 4 1 2이다.
뒤에서부터 for를 돌면서 앞의 숫자 < 그 뒤의 숫자 라면
2 < 4
다시 뒤에서부터 for를 돌면서 앞의 숫자(2)보다 처음으로 큰 수(4)를 찾는다
그리고 앞의 숫자와 찾은 수 둘을 swap 수행
5 3 4 2 1
앞의 숫자 인덱스 바로 앞 인덱스까지는 그냥 써주고
5 3 4
앞의숫자부터 마지막까지는 정렬한 후 써주면 된다
1 2

5 3 4 1 2