[LEETCODE 150] - 189 Rotate Array

LeetCode의 189번 문제인 "Rotate Array" (배열회전) 문제 입니다.

이문제를 풀면서 총 4가지의 방법을 연구해보고 풀어봤다.

문제에서 요구하는것은 다음과 같다.

 

주어진 정수 배열 nums을 단계만큼 오른쪽으로 회전시키세요 k. 단, 는 k음수가 아닙니다.

 

1. Reverse 기법(3번 뒤집기)

알고리즘 아이디어

오른쪽으로 k칸 회전은 

 

• 원래: [A | B]
  • A = 앞부분 (길이 n-k)
  • B = 뒷부분 (길이 k)
• 회전 후: [B | A]

이걸 뒤집기(reverse)로 만들수 있다.

1. 전체를 뒤집으면: reverse(A + B) = reverse(B) + reverse(A)
2. 앞쪽 k개(= reverse(B))를 다시 뒤집으면: B가 됨
3. 뒤쪽 n-k개(= reverse(A))를 다시 뒤집으면: A가 됨

결과적으로 [B | A] 완성.

 

정답 코드(Python)

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

 

 

코드 해석

1. K 정규화

k = k % len(nums)

 

k 가 배열길이보다 클수 있으니 줄어줌.

ex:) 길이가 7인데 k= 10이면, 실제회전은 3칸과 같음.

---

2. 전체 배열 뒤집기

l, r = 0, len(nums) - 1
while l < r:
	nums[l], nums[r] = nums[r], nums[l]
    l, r = l + 1, r - 1

 

투 포인터로 양 끝을 swap하면서 중앙으로 좁힘 → reverse(nums) 수행.

ex:) [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]

---

3. 앞쪽 k개 뒤집기

l, r = 0, k - 1
while l < r:
	nums[l], nums[r] = nums[r], nums[l]
    l, r = l + 1, r - 1

 

이제 배열의 앞쪽 k개는 원래 "회전 후 맨 앞에 올 덩어리(B)"인데 전체를 뒤집어 버려서 reverse(B) 상태라서

다시 뒤집어 B로 복구하는 과정이다.

 

ex :) k = 3 이면 [7,6,5,4,3,2,1]에서 앞 3개 뒤집기 → [5,6,7,4,3,2,1]

 

---

4. 나머지 뒤집기 

l, r = k, len(nums) - 1
while l < r:
	nums[l], nums[r] = nums[r], nums[l]
    l, r = l + 1, r - 1

 

뒤쪽 구간은 원래 앞부분이지만 전체 뒤집기로 reverse가 돼 있음.

다시 뒤집어 A로 복구

 

ex :) [5,6,7,4,3,2,1]에서 k = 3 이후 뒤집기 → [5,6,7,1,2,3,4]

---

2. Slicing

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

 

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

정답 코드(Python)

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]

---

3. 배열 순회

원래 배열의 길이만큼의 새로운 배열을 선언하고, 인덱스 k부터 1씩 증가시키면서 값을 복사한 후,

배열의 끝에 도달하는 경우 다시 배열의 처음으로 가서 이어서 값을 저장한다.

정답 코드(Python)

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]

---

4. 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]