10972: 다음 순열

import sys

N = int(input())
dest = list(map(int, sys.stdin.readline()[:-1].split(' ')))
tmp = [i for i in range(1, N+1)]
end_tmp = [i for i in range(N, 0, -1)]
result = []

flag = 0; exit_flag = 0
def dfs():
    global flag
    global exit_flag
    if len(result) == N:
        if flag == 1 and end_tmp != result:
            print(" ".join(map(str, result)))
            flag = 0
            exit_flag = 1
        if result == dest:
            flag = 1
            if result == end_tmp:
                print("-1")
                exit_flag = 1
        return
    for i in range(N):
        if tmp[i] not in result:
            result.append(tmp[i])
            dfs()
            result.pop()
            if exit_flag == 1: break
        if exit_flag == 1: break

dfs()

• 처음에 위의 코드와 같이 dfs로 접근했는데, runtime error (recursion error)가 발생함

• 그래서 위의 그림처럼 다음 순열을 구하는 방법을 찾아보았고, 그 결과는 아래와 같음
  1) 뒤에서부터 순회하며 뒤의 수(=t)가 앞의 수(=h)보다 큰 경우 둘을 swap함
  2) swap한 후, t의 뒤에 있는 수부터 끝까지 오름차순으로 정렬해줌

import sys

N = int(input())
perm = list(map(int, sys.stdin.readline()[:-1].split(' ')))

if perm == sorted(perm, reverse=True): print(-1)
else:
    for i in range(N-1, 0, -1):
        if perm[i-1] < perm[i]:
            for j in range(N-1, 0, -1):
                if perm[i-1] < perm[j]:
                    perm[i-1], perm[j] = perm[j], perm[i-1]
                    perm = perm[:i] + sorted(perm[i:])
                    print(" ".join(map(str, perm)))
                    break
            break