[리트코드] 189. Rotate Array

문제

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

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 <= 10**5
• -2**31 <= nums[i] <= 2**31 - 1
• 0 <= k <= 10**5

---

✔ 문제접근 #1 deque[통과] ⭕-> 요구사항 충족❌

Intuition
deque 자료구조를 사용하여 오른쪽으로 한 칸씩 k번 이동한다.

Algorithm

deque 자료구조인 dq에 nums 배열의 요소를 삽입한다. 오른쪽에서 pop하고 왼쪽에서 append하는 과정을 k번 반복한다. 그리고 다시 dq안의 요소들을 nums에 담아준다.

    def rotate(self, nums: List[int], k: int) -> None:
        # 회전을 위해 deque자료구조 사용
        dq = deque()
        
        for num in nums: # O(N)
            dq.append(num)

        # k번 반복
        for i in range(k): # O(K)
            dq.appendleft(dq.pop()) 
            
        # 기존 배열에 넘겨주기
        for i in range(len(nums)): # O(N)
            nums[i] = dq[i]

실행결과

Complexity Analysis

• 시간 복잡도 : O(N + K)
  • nums 배열을 dq에 옮김 O(N)
  • k번회전 O(K)
  • dq를 nums에 옮김 : O(N)
  • 그러므로 전체시간복잡도 : O(2N + K) = O(N + K)

• 공간복잡도 : O(N)
  
  • deque 자료구조 사용

---

✔ 문제접근 #2 해시[통과] ⭕ -> 요구사항 충족❌

Intuition
해시에(dict) 다음에 위치할 값과 그 요소를 저장한다.

Algorithm

(i + k) % n와 같이 나머지 연산을 통하여 k칸 오른쪽으로 이동했을 때의 다음 인덱스를 알 수 있다. 다음 인덱스를 key값으로 하고 해당 값을 value로 하는 dict를 생성한다.

 

그리고 dict를 살펴보며 key값에 해당하는 nums의 index에 요소를 넣어준다.

    def rotate(self, nums: List[int], k: int) -> None:
    
        d = dict()
        n = len(nums)
        
        # k번 이후에 위치할 index를 key, 그 값을 value로 하여 dict에 저장한다.
        for i in range(n): # O(N)
            d[(i + k) % n] = nums[i]
            
        
        for i in range(n): # O(N)
            nums[i] = d[i]

실행결과

Complexity Analysis

• 시간 복잡도 : O(N)
  • nums의 요소를 dict자료구조에 옮김 O(N)
  • d의 요소를 nums에 옮김 O(N)
  • 그러므로 전체시작복잡도 : O(N+ N) = O(N)

• 공간복잡도 : O(N)
  
  • dict자료구조를 사용

---

✔ 문제접근 #3 temp활용 [실패] ❌

Intuition

temp 변수를 활용하여 k번 전의 위치의 값을 하나씩 옮겨준다.

Algorithm

시작점의 값을 temp값에 저장해준다. 여기서는 시작점을 index = 0으로 지정한다.

시작점에 오게될 값을 시작점에 대입해준다. index = 0의 위치에 index = 4의 값인 5를 대입한다.

이제 시작점을 방금전에 대입한 index = 4로 바꾸고 위의 과정을 반복한다. 

    def rotate(self, nums: List[int], k: int) -> None:
    
        n = len(nums)
    
        # 0번 인덱스가 이동할 다음 인덱스
        # 그 값을 temp로 빼준다.
        pre_idx = 0
        temp = nums[pre_idx]
        
        for _ in range(n - 1):
            # 현재위치의 값에 옮겨질 이 전 값의 인덱스를 찾는다.    
            before_idx = (pre_idx - k) % n
            
            nums[pre_idx] = nums[before_idx]
            
            pre_idx = before_idx
        
        nums[pre_idx] = temp

실행결과

Analysis

배열을 한칸 이상씩 움직일 때 temp를 활용하여 자주 사용하는 방법이다. 하지만 이 문제에서는 이동전과 이동후의 위치가 모두 제각각 이기 때문에 다음과 같은 상황에서 반례가 발생한다.

반례 : [-1,-100,3,99] k = 2  -> 배열의 길이가 4이고 이동하는 k가 2칸이므로 index 0 에서 index 2로, index 2에서 index 0으로 다시 index 0에서 index 2로 .... 이와같이 반복이 일어나게 되고 index 1, 과 index 3은 움직이지 않게 된다.

그러므로 또 다른 방법을 생각해봐야 한다.

---

✔ 문제해답참조 #4 해시[성공] ⭕ -> 요구사항 충족 ⭕

Intuition

구간별로 데이터를 swap하여 문제를 해결한다.

Algorithm

[1, 2, 3, 4, 5, 6, 7] 배열 전체를 뒤집으면 [7, 6, 5, 4, 3, 2, 1]이 된다. 이 배열을 다시 k(k = 3)값을 기준으로 구분해놓으면 

[7, 6, 5] [4, 3, 2, 1] 와같이 되고, 이것을 원하는 결과값과 비교해보면

[5, 6, 7, 1, 2, 3, 4] 다음과 같이 위아래가 매칭되게 된다. 그러므로 처음에 뒤집은 전체배열에서 [0, 2] 구간을 뒤집고, [3, 6]구간을 뒤집으면 원하는 결과를 만들 수 있다.

    def swap(self, start, end, nums):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    
    def rotate(self, nums: List[int], k: int) -> None:

        n = len(nums)
        k = k % n

        # 전체를 뒤집어준다.
        self.swap(0, n - 1, nums)
        
        # k값 기준 왼쪽을 뒤집는다.
        self.swap(0, k - 1, nums)
        
        # k값 기준 오른쪽을 뒤집는다.
        self.swap(k , n - 1, nums)

실행결과

Complexity Analysis

• 시간 복잡도 : O(N)
  • swap메서드 총 3번 O(3N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(N)
  
  • dict자료구조를 사용

---

기타풀이 및 회고

공간복잡도 O(1)이 되도록 문제를 풀 수 있는지가 포인트였고, 다른 풀이를  참조하게 되었다. 배열을 뒤집어서 스왑하기 쉽게 구조를 바꾼다는 생각을 해내기가 어려웠던 것 같다. temp를 활용하며 밀어내는 방법 말고도 배열을 뒤집어서 생각해볼 수 있는 유연한 사고가 필요한 것 같다.

 

추가적인 주의사항으로는 k값은 배열의 길이 n이상이 되면 똑같은 위치로 옮겨지기 때문에 k = k % n를 이용하여 전처리 해주는 과정이 필요하다.