Python으로 푸는 LeetCode 189. Rotate Array

LeetCode 189. Rotate Array

주어진 배열과 숫자 k를 활용하여

배열을 k만큼 오른쪽으로 옮기는

코드를 짜야한다.

LeetCode에서 푼 문제 보기

LeetCode에서 문제 보기

github에서 코드보기

문제 예제

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]

문제 풀이

solution에도 잘 나와있지만, k 만큼 오른쪽으로 옮기는 것은 배열의 뒤에서 k만큼 자른 배열을 맨 앞에 이어붙이는 것과 같다.

단, 문제에서 in-place 공간을 활용하여 문제를 풀도록 하였다. 단순하게 k만큼 뒤에서부터 2개씩 자리를 바꾸는 방식은 답은 나올 수 있어도 시간 초과가 발생한다.

따라서 아래와 같이, 배열을 뒤집어 준다음에 배열의 앞에서 k만큼 뒤집고 그 나머지 배열끼리 또다시 순서를 뒤집어주면 된다.

파이썬의 notation을 사용하여 슬라이싱을 할 경우에는 새로운 배열로 deepcopy가 되는 것과 마찬가지라서 in-place 방식이 아니라는 점만 주의하면 된다.

파이썬 코드

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

#189. Rotate Array #189. Rotate Array 파이썬 #python 189. Rotate Array