- 다음순열
- 실버3
n과 순열이 주어진다. 순열을 오름차순으로 정렬할 때 다음의 순열을 출력한다. 마지막 순열일 경우 -1을 출력한다.
순서가 중요한 순열 문제다.
-
꼭대기 찾기
오름차순이 깨지는 지점을 찾는다. 배열의 뒤쪽부터 탐색하면서 현재요소(arr[i])와 그 전 요소(arr[i - 1])를 비교한다. arr[i - 1]이 arr[i] 보다 작은 경우를 만족하는 가장 큰 i를 찾는다. i -1이 꼭대기가 된다. 이러한 i가 존재하지 않으면 주어진 순열은 이미 마지막 순열이다. -
꼭대기와 꼭대기보다 큰 가장 작은수를 교환하기
꼭대기 이후의 숫자들중에서 arr[i-1]보다 큰 가장 작은 수를 찾아 교환한다. 이를 위해 끝에서부터 시작해서 arr[i - 1]보다 큰 수가 나올 때까지 순회한다. -
꼭대기 뒤집기
꼭대기 이후의 순열이 가장 작은 순열이 되도록 꼭대기 이후의 순열을 뒤집어준다.