📚 algo-wiki

Appearance

LeetCode 189 - Rotate Array ​

문제 설명 ​

주어진 정수 배열 nums를 오른쪽으로 k번 회전시켜라.
**In-place (O(1) extra space)**으로 구현하는 것이 Follow-up 조건.

예시 ​

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

접근 방법 ​

1⃣ ✨ 배열 Slice & Splice 이용 (O(n) extra space) ​

  • nums를 rotateValue 기준으로 두 부분으로 나눈 후, 재조합.
  • 직관적이고 가독성 좋지만, 추가 공간을 사용.
ts
function rotate(nums: number[], k: number): void {
  const rotateValue = nums.length - (k % nums.length)
  const remainPart = nums.slice(0, rotateValue)
  const rotatedPart = nums.slice(rotateValue)

  nums.splice(0, nums.length, ...rotatedPart, ...remainPart)
}

Time Complexity: O(n)
Space Complexity: O(n) (slice로 부분 배열 생성)

2⃣ 🛠️ 배열 Reverse 3번 이용 (O(1) extra space) ​

  • 전체 배열을 뒤집고, 앞부분 & 뒷부분 각각 다시 뒤집기.
  • 추가 배열을 만들지 않고, swap 연산만 사용.
ts
function rotate(nums: number[], k: number): void {
  const n = nums.length
  k = k % n

  const reverse = (start: number, end: number) => {
    while (start < end) {
      ;[nums[start], nums[end]] = [nums[end], nums[start]]
      start++
      end--
    }
  }

  reverse(0, n - 1) // 전체 뒤집기
  reverse(0, k - 1) // 앞 k개 뒤집기
  reverse(k, n - 1) // 나머지 뒤집기
}

Time Complexity: O(n)
Space Complexity: O(1)

비교 요약 ​

방법Time ComplexitySpace Complexity특징
Slice & Splice 사용O(n)O(n)직관적, 코드 가독성 좋음, 추가 공간 필요
Reverse 3번 (In-place) 사용O(n)O(1)메모리 효율적, Follow-up 조건 충족

참고 ​

  • Follow-up 조건을 만족하려면 반드시 O(1) extra space 풀이 사용 필요.
  • 배열의 회전은 뒤집기로 쉽게 구현할 수 있다는 점이 핵심.