[LeetCode] Rotate Array: 배열 회전 마스터하기 (Kotlin 풀이 및 최적화 전략)

오늘은 기술 면접 단골 문제인 LeetCode의 189. Rotate Array 문제를 함께 살펴보겠습니다. 배열을 다루는 기본적인 감각은 물론, 공간 복잡도 최적화 능력을 어필하기 아주 좋은 문제입니다.

---

📌 문제 개요

주어진 정수 배열 nums를 오른쪽으로 k단계만큼 회전시키는 문제입니다.

• Input: nums = [1,2,3,4,5,6,7], k = 3
• Output: [5,6,7,1,2,3,4]
• 핵심 조건: k는 음수가 아닐 수 있으며, 배열의 길이보다 클 수 있습니다. 또한, 가능하다면 O(1) 공간 복잡도(In-place)로 해결하는 것이 권장됩니다.

---

💡 첫 번째 접근: 임시 배열 활용하기 (Space O(n))

코드 구현 (Kotlin)

class Solution {
    fun rotate(nums: IntArray, k: Int): Unit {
        // 1. 원본 배열과 같은 크기의 임시 리스트 생성
        val temp = MutableList(nums.size) { 0 }

        // 2. 각 인덱스에 들어갈 위치 계산하여 할당
        for (index in nums.indices) {
            // (index + nums.size - (k % nums.size)) % nums.size 공식을 사용해
            // 회전 후 해당 자리에 와야 할 원본 데이터를 찾아옵니다.
            temp[index] = nums[(index + nums.size - (k % nums.size)) % nums.size]
        }

        // 3. 원본 배열에 결과 복사
        for (index in temp.indices) {
            nums[index] = temp[index]
        }
    }
}

🧐 분석 및 특징장점: 로직이 직관적입니다. 각 칸이 어디서 데이터를 가져올지 수식으로 명확히 정의됩니다.

• 시간 복잡도: $O(n)$ - 배열을 두 번 순회합니다.
• 공간 복잡도: $O(n)$ - 원본 배열과 동일한 크기의 temp 리스트가 필요합니다.

---

🚀 더 나은 방법은 없을까? (공간 최적화: In-place)

실제 개발 인터뷰에서는 "추가 메모리를 사용하지 않고(O(1)) 해결할 수 있나요?"라는 후속 질문이 들어올 확률이 매우 높습니다.
이때 사용할 수 있는 마법 같은 방법이 바로 배열 뒤집기(Reverse) 전략입니다.

뒤집기 전략 3단계

1. 전체 배열을 뒤집는다.
2. 앞부분 k개를 뒤집는다.
3. 나머지 뒷부분을 뒤집는다.

이 방식을 사용하면 별도의 메모리 할당 없이 배열 안에서 요소의 위치만 바꿔 문제를 해결할 수 있습니다.

최적화 코드 (Kotlin)

    class Solution {
      fun rotate(nums: IntArray, k: Int): Unit {
          val n = nums.size
          // k가 n보다 클 수 있으므로 나머지 연산 필수!
          val realK = k % n 

          // 1. 전체 뒤집기: [7, 6, 5, 4, 3, 2, 1]
          reverse(nums, 0, n - 1)
          // 2. 앞부분 k개 뒤집기: [5, 6, 7, 4, 3, 2, 1]
          reverse(nums, 0, realK - 1)
          // 3. 뒷부분 뒤집기: [5, 6, 7, 1, 2, 3, 4] -> 완성!
          reverse(nums, realK, n - 1)
      }

      private fun reverse(nums: IntArray, start: Int, end: Int) {
          var s = start
          var e = end
          while (s < e) {
              val temp = nums[s]
              nums[s] = nums[e]
              nums[e] = temp
              s++
              e--
          }
      }
  }

---

👨‍💻 시니어 엔지니어의 인사이트

1. k % nums.size를 잊지 마세요

면접관은 경계 조건(Edge Case) 처리를 유심히 봅니다.
만약 배열 길이가 3인데 k가 10이라면, 실제로는 1번 회전한 것(10 % 3 = 1)과 같습니다.
이 처리가 누락되면 성능 저하나 에러가 발생할 수 있습니다.

2. 공간 복잡도와 트레이드 오프처음 작성하신 O(n) 공간 방식은 코드가 명확하고 이해하기 쉽다는 장점이 있습니다.

반면 O(1) 방식은 메모리 효율은 극대화되지만 "배열을 세 번 뒤집는다"는 논리를 미리 알고 있어야 구현이 쉽습니다.
상황에 맞는 최적의 해법을 제시하고 이유를 설명하는 능력이 중요합니다.

✅ 한 줄 요약배열 회전 문제는 전체 뒤집기 후 부분 뒤집기 전략을 사용하면 추가 메모리 없이 $O(n)$ 시간 안에 해결 가능하다!

---

함께 보면 좋은 글

• [배열(Array)과 리스트(List)의 메모리 구조 차이][자주 나오는 투 포인터(Two Pointers) 알고리즘 정리]

출처

LeetCode 189. Rotate Array: https://leetcode.com/problems/rotate-array/