정의

다음 순열은 어떤 수열이 주어졌을 때, 같은 원소들로 만들 수 있는 모든 순열을 사전순으로 나열했을 때 "바로 다음"에 오는 순열을 찾는 알고리즘입니다. 추가 배열 없이 제자리에서 O(n)에 변환합니다.

핵심 특성

• ✓오른쪽에서 첫 번째 "감소가 끊기는 지점"(pivot)을 찾는 것이 핵심 - arr[i] < arr[i+1]인 가장 오른쪽 i
• ✓추가 메모리 없이 제자리(in-place)에서 동작 - 공간 복잡도 O(1)
• ✓단 한 번의 스캔과 교환, 그리고 뒤집기로 끝나므로 시간 복잡도 O(n)
• ✓수열이 완전한 내림차순(마지막 순열)이면 pivot이 없으며, 보통 처음 순열(오름차순)로 되돌린다

시간 복잡도