LeetCode Top Interview 150) Rotate Array

Question

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:

---

---

한 리스트nums과 정수k를 받아서 in-place로 k만큼 우측으로 회전시키는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        k %= n
        if n < 2 or k == 0:
            return
            
        idx,first_num = 0,nums[0]
        tmp = nums[-k:]
        nums[k:] = nums[:n-k]
        nums[:k] = tmp

• n : nums의 길이입니다.
• k의 값이 n길이만큼 회전해도 제자리이므로 나머지 값인 k%n을 k로 재정의합니다.
• 인덱스에 n값과 k값을 넣을 예정이기 때문에 인덱스 값에 혼란을 주는 예외를 미리 제외합니다. (길이 1 & 회전 x)
• 이후 전개는 간단합니다. 회전으로인해 앞으로 가게된 뒷 부분을 임시 변수로 저장합니다.
• 저장한 뒷 부분을 제외한 앞 부분을 새로운 뒷 부분으로 저장합니다.
• 나머지 앞 부분을 처음에 저장한 뒷부분으로 둡니다.

코드 자체는 쉽지만 문제에서 얘기한 공간복잡도O(1)을 만족하지 못하고 있었습니다.
꽤 오래 고민했지만 결국은 변수를 저장할 공간이 필요하고 이것은 어떠한 코드를 작성하더라도 지나갈 길이라는 생각이 들었습니다.

나중에 다시 돌아와서 고민할 부분으로 남겨두어야 겠습니다.