[리트코드] 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를 이용하여 전처리 해주는 과정이 필요하다.