다음 순열(Next Permutation)이란?
배열에 담긴 숫자들을 사전순(lexicographic order) 기준으로 바로 다음에 오는 더 큰 순열로 재배치하는 메서드를 구현해 보겠습니다. 만약 현재 배열이 이미 가능한 가장 큰 순열이라면, 더 큰 순열이 존재하지 않으므로 대신 오름차순으로 정렬된 가장 작은 순열로 되돌립니다. 이때 교체 작업은 반드시 제자리(in-place)에서 수행해야 하며, 별도의 추가 메모리를 사용하지 않아야 합니다.
예를 들어 왼쪽 열의 입력에 대해 오른쪽과 같은 출력을 얻습니다.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
알고리즘 동작 단계
- 초기화: found := False, i := 배열 길이 − 2
- 탐색: i ≥ 0인 동안 반복
- A[i] < A[i + 1]이면 found := True로 설정하고 반복을 종료합니다.
- 그렇지 않으면 i를 1씩 감소시킵니다.
- 예외 처리: found가 False라면(배열 전체가 내림차순인 경우) 배열 A를 오름차순으로 정렬합니다.
- 순열 갱신: found가 True라면 다음을 수행합니다.
- m := 인덱스 i + 1부터 배열 끝까지의 범위에서, 현재 값 A[i]보다 큰 원소들 중 가장 작은 값의 인덱스를 찾습니다.
- A[i]와 A[m]의 값을 서로 교환(swap)합니다.
- 인덱스 i + 1부터 끝까지의 원소들을 뒤집습니다(reverse).
동작 원리
핵심 아이디어는 배열을 뒤에서부터 훑으며 처음으로 오름차순 관계(nums[i] < nums[i+1])가 나타나는 지점을 찾는 것입니다. 이 지점보다 뒤쪽 부분 배열은 내림차순으로 정렬되어 있어, 그 구간만으로는 더 큰 순열을 만들 수 없습니다. 따라서 nums[i]를 뒤쪽 구간의 값들 중 nums[i]보다 큰 값 중 가장 작은 값과 교환한 뒤, 남은 꼬리 구간을 뒤집어 오름차순으로 만들면 사전순으로 다음 순열이 완성됩니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 제자리에서 동작하므로 추가 공간 복잡도는 O(1)입니다.
구현 예제
class Solution(object):
def nextPermutation(self, nums):
found = False
i = len(nums) - 2
while i >= 0:
if nums[i] < nums[i + 1]:
found = True
break
i -= 1
if not found:
nums.sort()
else:
m = self.findMaxIndex(i + 1, nums, nums[i])
nums[i], nums[m] = nums[m], nums[i]
nums[i + 1:] = nums[i + 1:][::-1]
return nums
def findMaxIndex(self, index, a, curr):
ans = -1
index = 0
for i in range(index, len(a)):
if a[i] > curr:
if ans == -1:
ans = curr
index = i
else:
ans = min(ans, a[i])
index = i
return index
ob1 = Solution()
print(ob1.nextPermutation([1, 2, 5, 4, 3]))
입력
[1,2,5,4,3]
출력
[1, 3, 2, 4, 5]