LeetCode 풀기 - 189. Rotate Array

189. Rotate Array

https://leetcode.com/problems/rotate-array/

Rotate Array - LeetCode

문제)

솔루션1)

공간복잡도를 O(N)으로 생각하면 굉장히 심플한 문제이다.

 

1) 임시 배열 생성

2) nums에서 k만큼 이동한 index에 값을 임시 배열에 넣는다

3) 임시 배열의 값을 nums에 복사

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        # 시간복잡도 : O(N)
        # 공간복잡도 : O(N)
                
        temps = [0] * len(nums)
        
        for i, n in enumerate(nums):
            temps[(i+k)%len(nums)] = n        
        
        for i, n in enumerate(temps):
            nums[i] = n

솔루션2)

여기에서 원하는 솔루션은 공간복잡도 O(1)을 만족해야한다.

아무리 짱구를 굴려도 공간복잡도 O(1)로 구현할 해결책이 보이지 않는다.

Discussion을 참조하였다.

 

풀이 방법은 아래와 같다. fact에 근거해서 풀어가는 솔루션이다.

k = 3

Original array               : 1 2 3 4 5 6 7

array 전체 역순             : 7 6 5 4 3 2 1

앞에 k개 만큼 역순         : 5 6 7 4 3 2 1

k+1부터 마지막까지 역순 : 5 6 7 1 2 3 4 ---> 정답

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        # 시간복잡도 : O(N)
        # 공간복잡도 : O(1)
        
        k %= len(nums)
        
        def reverse(nums, l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l, r = l + 1, r - 1
                
        r = len(nums) - 1
        
        reverse(nums, 0, r)
        reverse(nums, 0, k-1)
        reverse(nums, k, r)