LeetCode - 31. Next Permutation - swift

https://leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

 

주어진 숫자 배열을 통해, 그다음의 순열을 찾는 문제다.

만약 다음 순열이 존재하지 않는다면, 오름차순으로 정렬된 배열로 만들고, 

존재한다면 그 다음의 순열로 배열을 만든다. 

 

조금만 고민하면, 특징을 찾을 수 있다.

다음의 순열이 되기 위해서는, 배열의 끝부분부터 탐색하면서, 현재 위치보다 -1 한 위치와 크기 비교를 한다.

만약 arr[ i ] > arr[ i - 1 ] 이 존재한다면, i-1 부분부터 다시 재정렬하면 된다. 

 

즉, [ 1, 6, 5, 4 ] 인 경우에는 i 가 1일 때, arr[ i ] > arr [ i - 1 ] 이 성립한다. 

그러므로, i 가 0일때부터 재정렬하면 된다.

재정렬하기 위해서는, arr [ i ] 보다 크면서 가장 작은 값을 i에 넣어야 한다. 

그러므로, 1보다 크면서 가장 작은 값은 4이므로, 

4가 가장 맨앞에 위치해야 한다.

그다음에는 arr [ i .. < arr.count ] 에서 4를 제외한 값들을 정렬시켜 붙여주면 된다. 

 

class Solution {
    func nextPermutation(_ nums: inout [Int]) {
        var idx = -1
        for i in nums.indices.reversed() {
            if i > 0, nums[i] > nums[i-1] {
                idx = i-1
                break
            }
        }
        if idx == -1 {
            nums.sort(by: <)
        } else {
            var smallest = (101, idx)
            for i in idx+1..<nums.count {
                if nums[idx] < nums[i] {
                    if smallest.0 > nums[i] {
                        smallest = (nums[i], i)
                    }
                }
            }
            nums.swapAt(smallest.1,idx)
            let right = nums[idx+1..<nums.count].sorted(by: <)
            for i in idx+1..<nums.count {
                nums[i] = right[i-(idx+1)]
            }
        }
    }
}