🔹 Next Permutation
문자열 또는 수열에 대해 사전순으로 다음에 오는 가장 작은 순열 구하기
※ 사전순으로 가장 큰 순열은 내림차순으로 정렬된 상태입니다.
- cba는 abc의 사전순 가장 마지막 순열입니다.
✅ 뒤에서부터 봤을 때 내림차순이 깨지는 지점 찾기
오른쪽에서 볼때
🎯 [i] 오름차순 ➡️ 내림차순 깨짐
🎯 내림차순 [i]
※기존 : 사전순(오름차순) 정렬의 경우 오른쪽에서 볼때 내림차순
🗝️ 1. 오름차순 시점 찾기(i 찾기)
뒤에서(오른쪽)부터 보며 arr[i] < arr[i+1] 을 만족하는 가장 마지막 i 찾기
🗝️ 2. 교체 대상 찾기(j 찾기)
뒤에서(오른쪽)부터 보며 arr[i] < arr[j] 를 만족하는 가장 마지막 j 찾기 → swap
🗝️ 3. 시점 이후 오름차순 정렬하기(i+1부터 끝까지 뒤집기)
(내림차순 상태니까 뒤집으면 오름차순 → 가장 작은 순열 됨)
with me