[Leetcode/파이썬] 189. Rotate Array

Rotate Array

---

Given an integer array nums, 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]

 

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

 

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

        nums[:] = nums[-k:] + nums[:-k]
        
        ''' time_limit
        for _ in range(k) :
            target = nums[-1]
            nums[:] = [target] + nums[:-1]
        '''

이번엔 실수가 조금 있었다. 처음에 [:] 복사하는 걸 안했다고 문제가 풀리지 않아서 다른 분들의 코드를 보니 복사를 해야 문제가 해결되었다. 이후 문제 풀이를 진행. 

time_limit 부터

당연히 내가 가장 처음 생각했던 풀이다. k 가 10만번, 충분히 돌아갈 줄 알았는데 안돌아가서 실망했다. 그래서 내가 뭐 놓친게 있나 싶어서 봤더니 nums의 길이와 나눈 나머지 만큼 돌리는 걸 깜빡했다. 그래도 시간초과... ㅎㅎ...

그래서 for 문을 한 방에 해결할 수 있는 방법이 없을까...

풀이

• k %= n : 길이가 5인 리스트를 5번 오른쪽으로 회전을 시키면 처음 상태하고 똑같은 상태가 된다. 이를 방지하고자 이렇게 나누게 되면 10만번이든 100만번이든 길이 n 만큼은 돌렸다 치고 가 되기 때문에 연산 횟수를 확 줄일 수 있게 된다. 
• nums[:] = nums[-k:] + nums[:-k] : 회전한 만큼을 앞에다가 붙이고 회전하지 않은 리스트들을 뒤에다가 붙이는 작업이다. 이 과정은 for 문의 결과를 한 번에 표현이 된다. 

풀이를 보니까 "이 쉬운걸 왜 생각 못했지?" 라는 생각이 들었다.