[LeetCode 189] Rotate Array - TypeScript 문제 풀이 및 최적화

[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개의 부분으로 나눠서 뒤집으면 해결 가능!

1. 배열 전체를 뒤집는다 → [7,6,5,4,3,2,1]
2. 처음 k개의 원소를 다시 뒤집는다 → [5,6,7,4,3,2,1]
3. 나머지 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 설명을 배열 크기 + 회전 횟수 기준으로 작성하여 가독성 향상
✅ 추가적인 엣지 케이스도 테스트 가능

---

결론

이전에는 문제를 해결한 후 개선점을 찾아가며 최적화하는 방식이었어요. 하지만 이번에는 배열 회전의 패턴을 분석한 후 최적화된 방법을 한 번에 떠올릴 수 있었습니다. 🎯

배열 뒤집기 패턴은 회전 관련 문제에서 자주 사용되는 패턴이므로 기억해 두면 좋습니다! 🚀