2025-08-12
오늘 배운 것
Next Permutation
개념
- 현재 순열보다 크면서, 가장 가까운 순열
- 1, 2, 3 -> 1, 3, 2 -> 2, 1, 3 -> 2, 3, 1 -> 3, 1, 2 -> 3, 2, 1
- 마지막 순열에서 다음 순열이 없으면 정렬된 첫 순열로 돌아감
동작 원리
- 처음 배열은 오름차순 정렬 상태여야 함
- 뒤에서부터 연속해서 감소하는 구간을 찾아 감소 지적 인덱스 i 찾기
- i 보다 뒤에서 a[i]보다 큰 값 중 가장 작은 값의 인덱스 j 찾기
- swap(a[i], a[j])
- i + 1 부터 끝까지 오름차순 정렬
시간 복잡도
- O(N) : 스캔과 뒤집기만 진행
- 백트래킹으로 전체 순열 생성 시 O(N x N!) 가능