[알고리즘/Python] LeetCode 189. Rotate Array

문제

https://leetcode.com/problems/rotate-array/?envType=study-plan-v2&envId=top-interview-150

Rotate Array - LeetCode

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

---

💡접근방법 1:  잘라서 붙인다.

python의 편리한 배열 slicing 문법을 사용해서 배열을 자르고 붙이는 방법이다. 뒤에서부터 k개의 원소를 잘라서 배열의 앞부분으로 두고, 앞에서부터 n - k -1 인덱스 까지의 배열을 잘라서 뒤에 붙인다.

 

이때 주의할 점은 nums=[1,2]이고 k = 5처럼 k가 nums.length보다 커지는 경우가 있다는 것이다. 이를 해결하기 위해 k를 실제 유효한 회전횟수로 바꾸어주기 위해 배열의 길이로 나눈 나머지로 바꾸어준다. 배열의 길이만큼 회전시키면 원래 배열과 같아지기 때문에, 배열의 길이가 2인데 5번 회전시키는 경우 실제로는 5 % 2인 1만큼만 회전시키는 것과 같다.

class Solution(object):

    def rotate(self, nums, k):
        n = len(nums)
        k = k % n
        temp = nums[n - k:] + nums[:n - k]
        for i in range(len(nums)):
            nums[i] = temp[i]

 위의 for문의 temp배열의 값을 nums배열의 값으로 덮어쓰는 연산은 다음과 같이 대체할 수 있다. 

nums[::] = nums[n-k:] + nums[:n-k]

✔️시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 전체 배열을 슬라이싱하는 경우 해당 인덱스의 배열을 순회하면서 그 값을 새로운 배열에 복사하는 방식으로 이루어지므로 O(N) 시간이 소요된다. 또 배열을 합치는데 O(N), 합쳐진 배열의 값을 원래의 배열 nums로 옮기는데 O(N) 시간이 소요된다. 따라서 시간 복잡도는 O(N)이 된다.

 

공간 복잡도: O(N) . 배열을 슬라이싱 하는 경우 잘린 배열의 길이만큼 새로운 배열을 생성하고 값을 복사하는 형식으로 이루어진다. 배열을 두 부분으로 나누는데 실제 배열의 길이만큼의 공간이 필요하고, 또 잘린 배열을 다시 합치는데 실제 배열의 길이만큼 공간이 필요하다. 따라서 총 O(N) 공간 복잡도가 된다.

💡 접근방법 2:  배열을 순회한다.

 원래 배열의 길이만큼의 새로운 배열을 선언하고,  인덱스 k부터 부터 1씩 증가시키면서 값을 복사한후, 배열의 끝에 도달하는 경우 다시 배열의 처음으로 가서 이어서 값을 저장한다.

class Solution(object):

    def rotate(self, nums, k):
        n = len(nums)
        k = k % n
        temp = [None] * n
        for i in range(n):
            temp[(i + k) % n] = nums[i]
        for i in range(n):
            nums[i] = temp[i]

✔️시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 전체 배열을 한번 순회하여서 값을 복사하고, 새로운 배열의 값을 다시 원래 배열로 복사하는데 각각 O(N)시간이 소요되므로 O(N) 시간 복잡도를 가진다.

 

공간 복잡도: O(N). 기존 배열의 길이만큼 새로운 배열을 선언하기 때문에 O(N)만큼의 추가 공간이 필요하다.

💡접근방법 3:  deque 자료구조를 이용한다.

기존의 배열을 deque 자료구조를 이용하여 앞과 뒤에서 O(1) 시간에 넣고 뺄 수 있도록 하는 방식이다. 맨 뒤의 원소를 빼서 맨 앞에 넣는 작업을 k번 반복한다.

from collections import deque

class Solution(object):

    def rotate(self, nums, k):
        d = deque(nums)
        k = k % len(nums)
        for _ in range(k):
            popped = d.pop()
            d.appendleft(popped)
        for i in range(len(nums)):
            nums[i] = d[i]

✔️ 시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 기존의 배열을 사용해서 deque 타입의 새로운 선형 자료구조로 만드는 데 배열의 길이에 비례하는 시간 O(N)이 걸린다. deque 자료구조의 경우 맨 앞과 뒤에서 넣거나 빼는 연산은 O(1) 시간이 걸리기 때문에 k번 동안 맨 끝에서 원소를 빼서 앞에 넣는 연산은 O(1) 시간이 소요된다. 빅오 표기식은 가장 큰 시간 복잡도를 가지는 연산을 기준으로 하기 때문에 이 접근 방식은 O(N) 시간 복잡도를 가진다. 

 

공간 복잡도: O(N). 기존 배열 길이만큼의 deque 타입 데이터가 필요하기 때문에 O(N) 공간 복잡도를 가진다.

 

실행시간의 비교

---

 아래에서부터 접근방식1,  접근방식2, 접근방식3의 실행시간을 나타낸다. 따라서 실행시간을 기준으로 한다면 배열을 순회하는 접근방식 2가 가장 빠르고, deque자료구조를 사용하는 접근방식3이 가장 느리다.

⚒️ 개선:  공간복잡도를 O(1)로

위 세가지 방법은 모두 새로운 배열을 필요로 하며,  새로운 배열에 저장된 값을 기존의 배열에 복사하는 연산이 필요하다. 만약 O(1)  공간 복잡도를 가져야만 한다면, 다음과 같은 in-place 알고리즘을 사용할 수 있다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:    
        def swap_to_reverse(arr, i, j):
            while (i < j):
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
            return arr
        
      
        k %= len(nums)
            
        if (k > 0):
            swap_to_reverse(nums, 0, len(nums) - 1)  # rotate entire array
            swap_to_reverse(nums, 0, k - 1)          # rotate array upto k elements
            swap_to_reverse(nums, k, len(nums) - 1)  # rotate array from k to end of array

 Example1의 경우 nums가 [1,2,3,4,5,6,7] k = 3이다. 처음 swap_to_reverse() 호출시 nums =  [7,6,5,4,3,2,1]이 되고, 두번째로 swap_to_reverse()를 호출하면 [5,6,7,4,3,2,1]가 되고, 마지막으로 swap_to_reverse()를 호출하여 뒤의 n - k 개(4개)의 원소들을 뒤집으면 [5,6,7,1,2,3,4]가 되어 k번 회전된 배열을 얻을 수 있다.

 

 이 방법의 경우 시간 복잡도가 O(N) 공간복잡도가 O(1)로 위의 세가지 알고리즘보다 더 효율적이어 보이지만 실제로 실행시간은 188ms로 접근방법 1과 2보다 더 느린 것을 알 수 있다. 그 이유는 캐시 지역성 때문이라고 생각되는데, 접근방법 1과 2는 배열의 연속된 인덱스를 순차적으로 접근하는데 반해, 개선된 방법의 경우 떨어진 인덱스를 왔다갔다 하기 때문에 캐시 지역성의 이점을 활용할 수 없기 때문이다. 이에 대한 Chat-GPT의 자세한 설명은 https://kims-repo.tistory.com/4 에서 확인가능하다.

---

✅ 정리

◎ 공간 복잡도 제한 사항이 없다면 공간복잡도를 조금 희생하여 실행시간을 단축할 수 있다.

◎ 배열을 참조할때는 가능하면 인접한 인덱스를 참조하도록 하여 캐시 지역성을 이용하도록 하자.