[Medium] 배열 회전하기 - 189. Rotate Array

주어진 정수 배열 nums를 오른쪽으로 k번 회전시키는 것입니다. k는 음수가 아니며, 배열을 회전시킨 후의 결과를 출력해야 합니다.

예시

예시 1:

• 입력: nums = [1,2,3,4,5,6,7], k = 3
• 출력: [5,6,7,1,2,3,4]

설명:

1. 1번 회전: [7,1,2,3,4,5,6]
2. 2번 회전: [6,7,1,2,3,4,5]
3. 3번 회전: [5,6,7,1,2,3,4]

예시 2:

• 입력: nums = [-1,-100,3,99], k = 2
• 출력: [3,99,-1,-100]

설명:

1. 1번 회전: [99,-1,-100,3]
2. 2번 회전: [3,99,-1,-100]

제약 사항

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

추가 질문

1. 여러 가지 방법으로 이 문제를 해결할 수 있는지 고민해 보세요. 적어도 세 가지 방법이 있습니다.
2. O(1)의 추가 공간 복잡도로 이 문제를 해결할 수 있는지 생각해 보세요.

 

해결 방법

역순 정렬을 사용한 방법 (In-place 회전):

• 먼저 전체 배열을 역순으로 뒤집습니다.
• 그 후 앞쪽의 k개의 요소와 나머지 요소를 각각 다시 역순으로 뒤집습니다.
• 이 방법은 추가 공간을 거의 사용하지 않으며, 시간 복잡도는 O(n)입니다.

from typing import List


def reverse(nums: List[int], start: int, end: int):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        end -= 1
        start += 1


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