[LeetCode] Rotate Array - TypeScript 문제 풀이 및 최적화
문제 설명
LeetCode의 "Rotate Array" 문제는 배열을 오른쪽으로 k번 회전하는 문제입니다.
배열을 직접 수정해야 하며, 추가적인 공간을 사용하지 않고 O(1) 공간 복잡도로 해결해야 합니다.
처음 문제를 풀었을 때의 생각
처음에는 단순히 배열을 k번 반복해서 이동시키면 되겠다고 생각했어요. 하지만 직접 구현해 보니 비효율적이고 너무 오래 걸린다는 걸 깨달았어요.
이전에는 문제를 풀면서 개선점을 찾아 나가는 방식이었는데, 이번에는 문제의 패턴을 분석한 후 최적화된 방법을 한 번에 떠올렸습니다.
이 문제를 해결하는 과정에서 배열을 회전하는 문제에서 자주 사용되는 "배열 뒤집기" 패턴을 발견할 수 있었습니다.
비효율적인 접근 방식 (배열을 직접 이동시키기)
1️⃣ k번 반복하여 한 칸씩 이동 (O(N * k))
가장 직관적인 해결책은 k번 반복하면서 배열을 오른쪽으로 한 칸씩 이동하는 것입니다.
export function rotate(nums: number[], k: number): void {
k = k % nums.length; // k가 배열 길이보다 클 경우 처리
for (let i = 0; i < k; i++) {
nums.unshift(nums.pop()!);
}
}
이 방식은 작동은 하지만, 시간 복잡도가 O(N * k)로 매우 비효율적이에요. 배열 길이가 10^5이고 k도 10^5이면, 10^10번 연산해야 하므로 비현실적으로 오래 걸립니다. ❌
최적화 과정: 배열을 한 번에 회전하는 방법 찾기
2️⃣ 추가 배열을 사용 (O(N), O(N))
배열을 복사한 후 (i + k) % n 위치에 배치하면 훨씬 빠르게 해결할 수 있어요.
export function rotate(nums: number[], k: number): void {
const n = nums.length;
const rotated = new Array(n);
for (let i = 0; i < n; i++) {
rotated[(i + k) % n] = nums[i];
}
for (let i = 0; i < n; i++) {
nums[i] = rotated[i];
}
}
✅ 시간 복잡도 O(N), 공간 복잡도 O(N)
❌ 추가 배열 사용 → 공간 최적화 필요
3️⃣ 배열 뒤집기를 이용한 최적화 (O(N), O(1))
배열을 직접 이동하지 않고, 배열을 뒤집는 방식으로 해결할 수 있을까? 🤔
핵심 패턴 발견
배열을 k번 회전하는 건 두 개의 블록을 서로 교체하는 것과 같다!
nums = [1,2,3,4,5,6,7], k = 3
결과: [5,6,7,1,2,3,4]
💡 배열을 3개의 부분으로 나눠서 뒤집으면 해결 가능!
- 배열 전체를 뒤집는다 → [7,6,5,4,3,2,1]
- 처음 k개의 원소를 다시 뒤집는다 → [5,6,7,4,3,2,1]
- 나머지 n-k개의 원소를 다시 뒤집는다 → [5,6,7,1,2,3,4]
✅ 이제 정답이 나왔다!
최적화된 TypeScript 풀이 (O(N), O(1))
export function rotate(nums: number[], k: number): void {
k = k % nums.length; // 배열 길이를 초과하는 k 처리
function reverse(start: number, end: number) {
while (start < end) {
[nums[start], nums[end]] = [nums[end], nums[start]];
start++;
end--;
}
}
reverse(0, nums.length - 1); // 배열 전체 뒤집기
reverse(0, k - 1); // 처음 k개 뒤집기
reverse(k, nums.length - 1); // 나머지 뒤집기
}
✅ 시간 복잡도 O(N), 공간 복잡도 O(1)
✅ 추가 배열 없이 제자리에서 해결 가능
✅ 배열 뒤집기 패턴을 활용한 최적화된 방식
Jest 테스트 코드
describe("Medium 189: Rotate Array", () => {
it("rotates an array of length 7 by 3 positions", () => {
const nums = [1, 2, 3, 4, 5, 6, 7];
rotate(nums, 3);
expect(nums).toEqual([5, 6, 7, 1, 2, 3, 4]);
});
it("rotates an array of length 4 by 2 positions", () => {
const nums = [-1, -100, 3, 99];
rotate(nums, 2);
expect(nums).toEqual([3, 99, -1, -100]);
});
});
✅ it 설명을 배열 크기 + 회전 횟수 기준으로 작성하여 가독성 향상
✅ 추가적인 엣지 케이스도 테스트 가능
결론
이전에는 문제를 해결한 후 개선점을 찾아가며 최적화하는 방식이었어요. 하지만 이번에는 배열 회전의 패턴을 분석한 후 최적화된 방법을 한 번에 떠올릴 수 있었습니다. 🎯
배열 뒤집기 패턴은 회전 관련 문제에서 자주 사용되는 패턴이므로 기억해 두면 좋습니다! 🚀
'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode 122] Best Time to Buy and Sell Stock II - Greedy & DP 풀이 (0) | 2025.03.07 |
|---|---|
| [LeetCode 169] Majority Element - 보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm) 풀이 (0) | 2025.03.06 |
| [LeetCode 26] Remove Duplicates from Sorted Array - TypeScript 문제 풀이 및 최적화 (0) | 2025.03.04 |
| 맥북 모니터 받침대 솔직 리뷰! 목 건강까지 챙기는 거치대 (0) | 2025.03.03 |
| [LeetCode 27] Remove Element - TypeScript 문제 풀이 및 최적화 (0) | 2025.03.03 |
