## 문제
[Rotate Array - LeetCode](https://leetcode.com/problems/rotate-array)
## 코드
### 방법 1: Brute Force
문제 그대로 구현한다 (직관적이지만 unshift의 반복이...)
매번 배열의 마지막 요소를 꺼내 맨 앞에 넣음 (pop + unshift)
- Time Complexity : (pop (`O(1)`) + unshift(`O(n)`)) * k => `O(k * n)`
- Space Complexity : 추가 공간을 필요로 하지 않는다 => `O(1)`
```typescript
function rotate(nums: number[], k: number): void {
for (let count = 0; count < k; count++) {
const back = nums.pop() as number; // pop한 원소를 도로 넣기 때문에 nums가 비어있는 경우는 없음 -> undefined가 반환되지 않는다.
nums.unshift(back);
}
}
```
### 방법 2: 보조 배열을 사용하기
회전하면 각 원소들의 인덱스가 바뀐다. 어떻게 바뀌는지 규칙을 찾아보기.
`nums = [1,2,3,4,5,6,7], k = 3` 일 때 -> `[5,6,7,1,2,3,4]`
- 1: `nums[0]` -> `nums[3]`
- 2: `nums[1]` -> `nums[4]`
- 3: `nums[2]` -> `nums[5]`
- 4: `nums[3]` -> `nums[6]`
- 5: `nums[4]` -> `nums[0]`
- 6: `nums[5]` -> `nums[1]`
- 7: `nums[6]` -> `nums[2]`
=> `newIdx = (idx + k) % (nums.length)` 요런 규칙이 있다!
In-place로 바꿔주기에는 너무 복잡하기 때문에 새로운 배열을 만들어주고, 기존 배열에 옮겨넣어주기 (문제에서 의도한 방법은 아닐듯)
```typescript
function rotate(nums: number[], k: number): void {
const length = nums.length;
const rotated = Array(length).fill(0);
nums.forEach((value, i) => {
const newIndex = (i + k) % length;
rotated[newIndex] = value;
});
rotated.forEach((newNum, idx) => {
nums[idx] = newNum;
});
}
```
좀 더 멋진 코드를 위해서...
- rotated를 생성할 때 `reduce`를 썼다가 수정했다.
reduce는 누적 계산이 목적인 메서드.
잘 알려진 메서드의 목적에 맞게 써야 가독성이 높아진다. (여기서 갑자기 왜 누적을 하지? 하면서 인지 비용이 증가하게 됨)
```typescript
const rotated = nums.reduce((acc, cur, idx) => {
const newIdx = (idx + k) % length;
acc[newIdx] = cur;
return acc;
}, Array(length).fill(0))
```
- forEach보다는 for문이 빠르다. (참고: [JS loop benchmark](https://jsben.ch/js-loop-benchmark-girjy))
성능에 민감한 상황일 경우 for문을 고려하기
### 방법 3: 배열을 뒤집기 (In-place Reversal)
`nums = [1,2,3,4,5,6,7], k = 3` 일 때 -> `[5,6,7,1,2,3,4]`
이거를 자세히보면
- 뒤쪽 3개가 앞으로 왔고, (k개)
- 앞쪽 4개가 뒤로 왔다.
이런 형태적인(?) 특징을 알 수 있다.
배열의 원소의 인덱스를 옮기면서 추가 메모리 공간을 사용하지 못하는 경우에는 값을 덮어쓰게 될 수 있어서 어려운데, 이 때 취할 수 있는 전략이 **"배열을 뒤집기"**
`nums = [1,2,3,4,5,6,7], k = 3` 일 때 -> `[5,6,7,1,2,3,4]` 를 다시 보자.
1. 뒤에 있는 원소들이 앞에 왔으므로 일단 뒤집어준다. => `[7,6,5,4,3,2,1]`
2. 가장 왼쪽에 있어야 하는 5가 제자리에 오도록 배열의 일부를 뒤집어준다
=> 앞쪽 원소 3개(k개)를 다시 뒤집어준다 => `[5,6,7,4,3,2,1]`
3. 남은 원소들도 원래 순서로 돌아가도록 뒤집어준다
=> 뒤쪽 원소 4개(n-k개)를 다시 뒤집어준다 => `[5,6,7,1,2,3,4]`
Javascript에는 배열을 일부만 뒤집는 메서드가 없기 때문에... 직접 구현해줘야 한다.
```typescript
function reverse(nums: number[], startIdx: number, endIdx: number): void {
while (startIdx < endIdx) {
[nums[startIdx], nums[endIdx]] = [nums[endIdx], nums[startIdx]];
startIdx++;
endIdx--;
}
}
function rotate(nums: number[], k: number): void {
const n = nums.length;
k = k % n; // n <= k 인 경우 대비
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
```
reverse 함수 구현과 관련된 JS 지식들
- [[비구조화 할당]] (정리 예정)
- [[데이터 타입#값에 의한 복사 vs 참조에 의한 복사|Pass-by-Reference]]
## 참고
[[Two Pointers]]