LeetCode알고리즘 Rotate Array문제

알고리즘 문제를 풀다가 좋은 솔루션을 배우게 되어 포스팅하려 합니다.
오늘은 포스팅할 문제는 189번이고 난이도는 중간 난이도입니다.

문제를 살펴봅시다.

배열이 주어지면 배열을 오른쪽으로 k 단계씩 회전합니다.
여기서 k는 음수가 아닙니다.
- 가능한 많은 해결책을 찾아보세요. 이 문제를 해결하는 방법은 적어도 3가지 존재합니다. 
- 너는 인플레이스로 공간 복잡도 O(1)로 처리할 수 있니

제약은 아래와 같습니다.

예제를 살펴보겠습니다.

아래 코드는 제가 처음 풀었던 방식입니다.

func rotate(_ nums: inout [Int], _ k: Int) {
    for _ in 0..<k {
        var end = nums[nums.count - 1]
        for i in stride(from:nums.count - 1, to: 0, by: -1) {
            var temp = nums[i - 1]
            nums[i] = temp
        }
        nums[0] = end
    }
}

K번 회전하기 위해 첫 번째 루프를 들어갑니다. (K번 실행)
마지막 값을 저장해줍니다.
그리고 루프를 들어가고 하나 앞칸의 값을 가져와서 뒤에 넣어줍니다.
(뒤에서부터 값을 변경해줍니다.)
(오른쪽으로 회전시키기 때문에 뒤에서부터 값을 변경해 줌) 
루프가 끝나면 저장했던 마지막 값을 첫 번째에 넣어줍니다.

잘 되는 줄 알았으나 시간 복잡도는 O(n^2)이 되겠네요.
그래서 타임 초과가 나왔습니다.

근데 테스트 케이스 값이 진짜 진짜 너무 많아서 얼마나 걸리는지 테스트하려다가 노트북이 가열되더라고요.
심지어 K값도 몇천 번이었음.
(내 노트북도 너무하고 테스트 케이스도 너무하고)

여기서 코드를 개선해야 했어요.
일단 시간 복잡도가 가장 문제니 시간 복잡도를 줄여줍니다.
조금이라도 덜 실행되게 만들어야해.

아래 코드를 살펴봅시다.

func rotate(_ nums: inout [Int], _ k: Int) {
    guard nums.count > 0 && k > 0 else {
        return
    }
    let k = k % nums.count
    guard k != 0 else {
        return
    }
    reverse(&nums, 0, nums.count - 1)
    reverse(&nums, 0, k - 1)
    reverse(&nums, k, nums.count - 1)
}

func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) {
    if start < 0 || end > nums.count || start >= end {
        return
    }
    
    var startIndex = start
    var endIndex = end
    
    while startIndex < endIndex {
        nums.swapAt(startIndex, endIndex)
        startIndex += 1
        endIndex -= 1
    }
}

먼저 nums.count가 0 이하 거나 K가 0 이하면 리턴해줍니다.
새로운 k에 값을 설정해줍니다. (이 새롭게 할당된 k를 기준으로 전환을 해주기 때문)
reverse라는 함수를 총 3번 호출해줍니다.
- 처음부터 끝까지 전환
- 처음부터 k - 1까지 전환
- k부터 끝까지 전환
reverse함수 내에는 startIndex와 endIndex를 만들어서 각각을 스왑 해주는 코드가 들어있습니다.

첫 번째 예제를 실행해보면 아래와 같이 전환된다고 생각해주시면 됩니다.
nums = [1,2,3,4,5,6,7] k = 3

처음부터 끝까지 전환
nums = [7,6,5,4,3,2,1]
처음부터 k - 1까지 전환
nums = [5,6,7,4,3,2,1]
k부터 끝까지 전환
nums = [5,6,7,1,2,3,4]

총 3번의 함수 호출로 배열 전환을 시킬 수 있었습니다.

제출해보면 아래와 같이 결과가 나옵니다.

leetcode.com/problems/rotate-array/