[백준 10872] 다음 순열

문제

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을 출력한다.

---

풀이

처음에 문제를 보고 재귀를 통한 완전탐색으로 비교를 통해 입력받은 순열을 찾고 다음 순열을 출력할 생각을 하였지만 N값의 범위를 보고 다른 방법을 생각하였다

먼저 파이썬에서 지원하는 itertools.permutations 라이브러리 함수를 통해 문제를 풀어보기로 했다

# 다음 순열
import sys
import itertools

N = int(sys.stdin.readline())
compare = list(map(int,sys.stdin.readline().split()))

# itertools를 사용하여 다음 순열 출력
if compare == sorted(compare,reverse=True):
    print(-1)
else:
    ans = list(itertools.permutations(compare))[1]
    print(*ans)

어느정도 예상했지만 순열을 list화하는 과정에서 메모리 초과가 뜬다

 

next permutation을 구현해보자

# 다음 순열
import sys
import itertools

N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))

# 마지막 수열일 경우 -1
if arr == sorted(arr,reverse=True):
    print(-1)
    exit(0)

line_value = arr[N-1]
line_index = 0
swap_idx = 1

# 뒤에서부터 시작하여 오름차순의 마지막 인덱스 i 탐색
for e in reversed(arr):
    if line_value > e:
        break
    line_value = e
    line_index += 1

# i~N중 arr[i]보다 큰 가장 작은 수의 인덱스 j를 탐색
for m in reversed(arr[-line_index:]):
    if m > arr[-line_index-1]:
        break
    swap_idx += 1

# i-1과 j swap
swap = arr[-line_index-1]
arr[-line_index-1] = arr[-swap_idx]
arr[-swap_idx] = swap

# i~N인덱스 뒤집어서 재결합
arr = arr[:-line_index] + list(reversed(arr[-line_index:]))
print(*arr)