leetcode 189

Rotate Array, 문제는 정말 간단하다. 그렇지만 시간복잡도를 O(1)으로 풀기 위해서는 약간의 아이디어가 필요한데, 배열의 item 값을 바꿀 때, item을 가르키는 prev을 지정해야하고, cnt로 전체 item을 탐색하고 있는지 추적해야한다. start는 n//k값이다. 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        
        # start defines 
        start = cnt = 0
        while cnt < n:
            # prev는 바뀌기 이전의 value를 지정
            curr, prev = start, nums[start]
            
            while True:
                nextIdx = (curr + k) % n
                nums[nextIdx], prev = prev, nums[nextIdx]
                curr = nextIdx
                cnt += 1
                
                if start == curr:
                    break
            start += 1