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만큼 오른쪽으로 회전한 상태