189. Rotate Array ☆★★★★

189. Rotate Array

 

내 풀이

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        for i in range(0, k):
            tmp = nums[n-1]
            nums[1:] = nums[:-1]
            nums[0] = tmp

 

Time Limit Exceeded 발생

 

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?

 

https://youtu.be/BHr381Guz3Y?si=t32wX0guYif6IukJ

 

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Step 1: k 값 조정 (배열 길이를 넘어가는 경우를 대비)
        # k가 배열의 길이보다 클 경우, k를 배열 길이로 나눈 나머지로 계산
        k = k % len(nums)

        # Step 2: 전체 배열을 역순으로 정렬
        # 이 과정으로 배열이 뒤집혀 순서가 반전됨
        # nums = nums[::-1] 과 같음
        l, r = 0, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]  # 왼쪽과 오른쪽 요소를 교환
            l, r = l + 1, r - 1  # 인덱스를 가운데로 이동
        # 예: [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]

        # Step 3: 배열의 처음부터 k-1까지 부분 배열을 다시 뒤집음
        # 이 과정으로 앞쪽 k개의 요소가 올바른 순서로 복원됨
        l, r = 0, k - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]  # 부분 배열 요소 교환
            l, r = l + 1, r - 1  # 인덱스를 가운데로 이동
        # 예: [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]

        # Step 4: 배열의 k부터 끝까지 부분 배열을 다시 뒤집음
        # 이 과정으로 뒤쪽 부분 배열이 올바른 순서로 복원됨
        l, r = k, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]  # 부분 배열 요소 교환
            l, r = l + 1, r - 1  # 인덱스를 가운데로 이동
        # 예: [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]

        # 최종 결과: 배열이 k만큼 오른쪽으로 회전한 상태

 

내 코드

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Step 1: k 값 조정 (배열 길이를 넘어가는 경우를 대비)
        # k가 배열의 길이보다 클 경우, k를 배열 길이로 나눈 나머지로 계산
        k = k % len(nums)

        # Step 2: 전체 배열을 역순으로 정렬
        # 이 과정으로 배열이 뒤집혀 순서가 반전됨
        # nums = nums[::-1] 과 같음
        print(nums)
        nums = nums[::-1]
        print(nums)
        # 예: [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]
        nums[:k] = nums[:k][::-1]
        print(nums)
        nums[k:] = nums[k:][::-1]
        print(nums)
        return nums.copy()

 

좋습니다! 코드의 전체적인 로직은 배열을 오른쪽으로 k칸 회전시키는 문제에 대해 매우 잘 설계되어 있습니다.
다만, 두 가지 중요한 문제점이 있습니다:

---

❗ 문제점 요약

1. in-place 수정이 안 됨

nums = nums[::-1]  # 이렇게 하면 nums는 새로운 리스트를 가리키게 됨 (원본이 바뀌지 않음)

• 이 방식은 nums 자체를 새로운 객체로 바꾸는 것이므로,
• 외부에서 참조하는 nums 리스트는 변경되지 않습니다 (리스트 주소가 바뀌기 때문).

❗문제에서 요구하는 것은 in-place 수정을 하라는 것. 즉, nums 리스트의 내용을 직접 바꿔야 합니다.

---

2. return nums.copy()는 불필요

• 문제에서 리턴하지 말라고 되어 있습니다.
• nums를 직접 수정해야 하며, 반환하면 오히려 채점 시스템에서 오류가 날 수 있습니다.

 

✅ 2차 수정

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n  # k가 배열 길이보다 클 수 있으므로 조정

        # Step 1: 전체 뒤집기
        nums.reverse()

        # Step 2: 앞쪽 k개 뒤집기
        nums[:k] = reversed(nums[:k])

        # Step 3: 나머지 뒤집기
        nums[k:] = reversed(nums[k:])

 

❗ 문제점 요약

✅ 1. reversed(nums)는 리스트를 in-place로 뒤집지 않음

nums = reversed(nums)

• reversed()는 iterator 객체를 반환하며,
• 원본 리스트인 nums를 변경하지 않습니다.
• 게다가 nums 자체를 덮어써버려 이후 슬라이싱도 불가능해짐 (nums[:k] 불가).

---

✅ 2. nums[:k] = reversed(nums[:k])는 원래 리스트가 iterator라서 실패함

• 위 줄 실행 전에 nums는 더 이상 list가 아니고, reversed 객체입니다.
• 이 상태에서 슬라이싱을 시도하면 오류가 발생합니다.

 

✅ 최종 수정 코드 (in-place, 안전한 방식)

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        """
        # Step 1: k 값 조정 (배열 길이를 넘어가는 경우를 대비)
        # k가 배열의 길이보다 클 경우, k를 배열 길이로 나눈 나머지로 계산
        """
        k = k % len(nums)

        # in-place reverse 함수
        def reverse(start: int, end: int):
            # while 0<end and start < len(nums) and start < end:
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        
        """
        # Step 2: 전체 배열을 역순으로 정렬
        # nums = nums[::-1] 과 같음
        # 예: [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]
        """        
        reverse(0, len(nums)-1)
        
        """
        # Step 3: 앞쪽 k개 뒤집기
        # nums[:k] = nums[:k][::-1] 과 같음
        # 예: [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
        """        
        reverse(0, k-1)
        
        """
        # Step 4: 나머지 뒤집기
        # nums[:k] = nums[:k][::-1] 과 같음
        # 예: [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]
        """        
        reverse(k, len(nums)-1)
        # print(nums)