[LeetCode] Next Permutation

문제

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Approach

뒤에서 부터 배열을 읽어 숫자가 작아지기 시작하는 지점을 찾고

그 이후 지점에서 숫자가 작아지기 시작하는 지점의 값보다는 크고 그 중에서는 가장 작은 수를 골라

숫자가 작아지기 시작하는 지점과 자리를 바꾸고 그 뒤에 값은 sorting했다.

그런데 이렇게 하니 performance가 최하위 수준..

Sorting 말고 숫자 순서를 뒤집으면 된다. (숫자가 작아지기 시작하는 지점보다 뒤는 계속 커지는 수이기 때문)

수동으로 뒤집었더니 빨라졌다

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_NextPermutation.cpp

chi3236/algorithm

https://github.com/chi3236/algorithm/blob/master/LeetCode_NextPermutation2.cpp

chi3236/algorithm