[BOJ/Python3] 10972번 다음 순열

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

알고리즘 분류
수학
조합론

from itertools import permutations as pm
input = __import__('sys').stdin.readline

N = int(input())
num_tuple = tuple(map(int, input().split()))
state = 0

for i in pm(range(1,N+1),N):
    if num_tuple == tuple(range(N, 0, -1)):
        print(-1)
        break
    if state:
        print(' '.join(map(str, i)))
        break 
    if i == num_tuple:
        state = 1

 

문제풀이

pm(range(1,N+1),N)은 어차피 원하는대로 정렬되어 있으므로
앞에서부터 하나씩 주어진 수열과 비교해 주어진 수열이 나오면 다음 반복에서 정답 수열을 출력하는 알고리즘
==> 시간 복잡도가 N!을 넘어가면서 주어진 범위(1 ≤ N ≤ 10,000)에서 시간 초과

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

if N == 1:
    print(-1)

for i in range(N-2, -1, -1):
    if num_lst == list(range(N, 0, -1)):
        print(-1)
        break
    if not num_lst[i:] == sorted(num_lst[i:], reverse=True):
        for j in range(N-1, i, -1):
            if num_lst[j] > num_lst[i]:
                num_lst[j], num_lst[i] = num_lst[i], num_lst[j]
                break
        ans = num_lst[:i+1] + sorted(num_lst[i+1:])
        print(' '.join(map(str, ans)))
        break

permutation 모듈을 버리고 새로운 알고리즘 설계

N == 1일때 출력은 반드시 -1 이므로 따로 처리
주어진 수열의 뒤에서부터 반복 시작(index N-2 부터 0까지)

• 주어진 수열이 N부터 1까지의 내림차순 수열이라면 -1 출력하고 break
• 다음 순열을 구하기 위해서 바꿔야할 부분은 뒤에서부터 처음으로 내림차순이 아니게 되는 부분까지임을 이용
• 내림차순이 깨진 index = i 인 수에 대해 다음 과정 수행

• i 이후에 나오는 수들은 모두 내림차순이므로 뒤에서부터 i 보단 크지만 i 이후의 수들 중 가장 작은 수 탐색
• 해당 수의 index = j 이므로 index = i 인 수와 index = j 인 수 교체
• ans = (i 까지의 수열 리스트) + (i 이후의 수를 오름차순으로 정렬한 수열 리스트)

• ans 출력 후 break