[BOJ] 10972 - 다음 순열(next permutation)

문제

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

10972번: 다음 순열

1부터 N까지의 수로 이루어진 순열을 입력으로 받아, 사전 순으로 다음에 오는 순열을 구하여라.

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

 

예시 )

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

입력 첫째 줄은 N을, 둘째 줄은 순열이 주어진다. 입력 받은 순열이 가장 마지막 순열인 경우에는 -1을 출력한다.

 

풀이

1. 순열의 오른쪽 끝에서부터 순회하여, 내림차순 배열이 끝나는 지점을 찾는다.

[2, 3, 6, 5, 4, 1]라는 순열이 있는 경우, 2 3 / 6 5 4 1와 같이 나뉘는 지점을 찾는다.

순열의 앞을 2 3으로 고정시켰을 때, 6 5 4 1 이후로 올 수 있는 순열이 없기 때문에, 다음 순열이 오기 위해서는 3이 다른 숫자로 변경되어야 한다.

 

즉, nums[n - 1]에서부터 시작해서 nums[i - 1] > nums[i]가 되는 지점을 찾는다. 이때, i - 1이 변경되는 지점이다.

 

2. 자리를 교체할 수를 찾는다.

[2, 3, 6, 5, 4, 1]라는 순열의 경우, 4에 해당한다. 순열의 오른쪽 끝에서부터 순회하여 3보다 큰 수를 찾으면 된다.

 

즉, nums[n - 1]에서부터 시작해서 nums[i - 1] < nums[j]가 되는 지점을 찾는다.

3. 1, 2에서 찾은 두 수의 위치를 교환한다.

 

즉, nums[i - 1]와 nums[j]의 위치를 교환하다.

4. 순열 [2, 4, 6, 5, 3, 1]에서 2 4를 고정시켰을 때 6 5 3 1은 가장 마지막에 올 수 있는 숫자 조합이다. 가장 처음으로 올 수 있는 숫자 조합이 되기 위해서는 6 5 3 1의 순서를 뒤집어야 한다. 

즉, nums[:i] 와 nums[i:]를 역순으로 배열한 리스트를 합친 것이 다음 순열에 해당한다.

 

코드

import sys

# 입력
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

# 1. 내림차순이 끝나는 지점 찾기
i = n - 1
while i > 0 and nums[i - 1] > nums[i]:
    i -= 1
# 입력 순열이 마지막 순열이면 -1 출력
if i <= 0:
    print(-1)
    exit()

# 2. 위치를 교환할 수 찾기
j = n - 1
while nums[j] < nums[i - 1]:
    j -= 1
    
# 3. 두 수 교환
nums[i - 1], nums[j] = nums[j], nums[i - 1]

# 4. 순열 정렬 후 출력
print(*(nums[:i] + nums[i:][::-1]))

 

 

---

참고 문서

https://otee.dev/2021/10/27/next-permutation.html

https://pangtrue.tistory.com/327