[Leetcode] 189. Rotate Array

21.11.23
Solved at re-trial

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Solution

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k==0:
            return
        
        startIdx=0
        cnt=0
        l=len(nums)
        
        while cnt!=len(nums):
            idx=startIdx
            nextValue=nums[(idx+k)%l]
            nums[(idx+k)%l]=nums[idx]
            idx=(idx+k)%l
            cnt+=1
            
            while idx!=startIdx and cnt!=len(nums):
                tmp=nums[(idx+k)%l] 
                nums[(idx+k)%l] = nextValue            
                nextValue=tmp
                cnt+=1
                idx=(idx+k)%l
            
            
            startIdx+=1

iteration. O(n), O(1)

안 풀리다가 밥 먹고 오니까 바로 풀림. 처음에 잘못된 아이디어를 얼마나 빨리 버리는게 중요한가?

도중에 idx+=k만 했다가 한 번 에러나고, 마지막에 %l 덧붙여줘서 통과함. 코드 구현보다 아이디어 빨리 떠올리는게 중요했음. 가져온 예제로 손으로 그리면서 했음. 특히 k가 l의 약수가 되는 상황을 커버하기 위해 startIdx와 cnt 사용 사용.

Best Solution

https://leetcode.com/problems/rotate-array/discuss/202250/4-python-solutions

class Solution(object):
    def rotate(self, nums, k):
        k = k % len(nums)
        dupnums = [0] * len(nums)
        for i in range(len(nums)):
            dupnums[(i + k) % len(nums)] = nums[i]

        nums[:] = dupnums # copy dupnums to nums

O(n), O(n)

공간 n만큼 사용. nums 카피하는 것 마지막에 기억해야. 공간 사용하는게 구현은 더 쉬움. 아이디어도 떠올리기 좋고.

class Solution(object):
    def rotate(self, nums, k):
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

아이디어가 훨씬 좋아서 코드도 더 간결함. 숫자 자체를 관찰하면 만들 수 있을지도.