Leetcode 189. Rotate Array (O(1) 제약조건)

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

Rotate Array - LeetCode

 

---

이 문제는 간단해 보이지만 O(1)의 공간을 이용해서 풀어야 하는 문제였습니다.

즉, 별도의 공간을 할당해서 임시로 값을 저장하는 장치 같은것은 사용하지 말라는 문제였는데요

 

저는 처음에 deque.rotate() 를 이용해서 풀다가 nums 에 in-place로 접근해야 하는 것을 깨닫고 헤맸던 문제였습니다.

 

---

Reverse 풀이)

Original List             : 1 2 3 4 5 6 7
Reversing all numbers     : 7 6 5 4 3 2 1
Reversing first k numbers : 5 6 7 4 3 2 1
Revering last n-k numbers : 5 6 7 1 2 3 4

 

이 문제의 핵심은 reverse 를 이용하는 것이었습니다.

처음에 nums[k:] + nums[len(nums)-k] 를 시도했으나, 답안으로 인정이 안되더라구요

 

위처럼 처음에 전체를 reverse 하고, 앞의 k 개만 reverse 하고 나머지 뒤의 숫자들을 reverse 하는 코드를 짜보겠습니다

 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        
        def reverse(nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end],nums[start]
                start +=1
                end -= 1
                
        k %= len(nums)
        reverse(nums,0,len(nums)-1)
        reverse(nums,0,k-1)
        reverse(nums,k,len(nums)-1)

 

reverse함수를 통해서 start와 end 라는 포인터를 지정해주고 서로 만날때까지 자리를 바꿔주는 형식을 취했습니다.

 

여기서 다른 분의 코드에서 k %= len(nums)라는 코드를 가지고 왔는데요

이게 뭔지 처음에는 이해가 안 갔는데 뜻을 해석하고 보니 이해가 됐습니다.

%=은 좌측의 값을 len(nums)로 나눈 나머지를 뜻합니다. 

k개인 만큼 일반적인 경우라면  len(nums)보다 k 가 작기 때문에 k 값이 그대로 사용되게 됩니다.

 

하지만 여기서 len(nums)가 k보다 작은 (k=2,  nums=[-1])  같은 경우에는 [-1]을 반환할 장치가 필요합니다.

그 장치가 바로 k %= len(nums)가 됩니다.

 

이 외에는 reverse함수를 통해서 위에서 했던 3단계를 코드화했습니다.

 

---

이렇게 시간적, 공간적 제약이 있는 문제를 풀기 위해서는 Big O notation의 time,space complexity 에 대한 이해가 필수적인 것 같습니다 !! Cheatsheet를 참고하면서 개념에 익숙해져야겠습니다

 

2022.10.05 - [데이터 공부 TIP] - 알고리즘, Big O Notation Cheatsheet