Day006 - 189. Rotate Array

189. 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:
        k = len(nums) - (k % len(nums))
        nums = (nums + nums[:k])[k:]
        # 이 코드로는 nums 자체를 수정할 수 없음.
        
    # 두 번째 코드
    def rotate(self, nums: List[int], k: int) -> None:
        k = k % len(nums)
        for _ in range(k):
            a = nums.pop()
            nums.insert(0, a)
        # 너무 느림

주어진 array를 k만큼 rotate하는 문제이다.

우선 처음 생각한 방법으로는 회전시킬 만큼 list를 잘라낸 후에 통째로 옮겨 이어붙여서 회전시키는 방법이였는데, 내가 작성한 코드로는 nums list 자체를 수정할 수 없었다.

따라서 두 번째 방법을 생각해 보았는데, 회전하는 만큼 pop()으로 꺼내서 insert()로 맨 앞에 하나씩 넣어주는 방법이였다. 하지만 list.insert()는 \(O(N)\)의 시간복잡도를 가지기 때문에, 최악의 경우에는 \(O(N^2)\)의 시간복잡도를 가지게 되므로 다른 방법을 사용해야만 했다.

# 세 번째 풀이
class Solution:
    def reverse_list(self, nums: List[int], start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

    def rotate(self, nums: List[int], k: int) -> None:
        # 3회전 O(N)
        k = k % len(nums)
        nums.reverse()
        self.reverse_list(nums, 0, k-1)
        self.reverse_list(nums, k, len(nums)-1)

마지막으로는 3번의 reverse를 통해 문제를 해결했다.

먼저 주어진 list의 원하는 인덱스부분을 하나씩 뒤집어주는 reverse_list 함수를 정의한 후에 총 3번의 reverse를 시행하였다.

주어진 list가 [1, 2, 3, 4, 5, 6, 7]이고, k=3이라고 할 때를 예로 들어보면

1. 먼저 전체 list를 뒤집어준다 : [7, 6, 5, 4, 3, 2, 1]
2. 앞의 3개를 뒤집는다. : [5, 6, 7, 4, 3, 2, 1]
3. 남은 4개를 뒤집는다. : [5, 6, 7, 1, 2, 3, 4]

# Time Complexity : \(O(N)\)

*추가사항*

문제를 다 풀고나서 알게 되었는데, 첫 번째 방법으로도 nums list 자체를 수정할 수 있는 방법이 있었다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k = len(nums) - (k % len(nums))
        
        nums = (nums + nums[:k])[k:] # 수정 불가능
        nums[:] = (nums + nums[:k])[k:] # 수정 가능

nums와 nums[:]의 차이인데,

1. “nums=” 는 nums변수에 새로운 값을 참조하도록 하는 것이고(기존의 list 대신 새로운 list를 가리키게 됨)
2. “nums[:]=” 는 nums list를 새로운 값으로 덮어 씌우는(list 자체가 참조하는 memory 주소는 변하지 않음)것이다.

따라서 nums[:]를 사용하면 nums list 자체를 수정하여 문제를 해결할 수 있다!