[코딩/LeetCode150-(6)] Rotate Array (189)

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python3을 사용합니다.

 

 

 

 

 

난이도: Medium

키워드: Array

 

 

🔒 문제

문제 원문: https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150 

 

정수 배열 nums가 주어질 때 주어진 음이 아닌 정수 k에 대해서 k 번만큼 배열을 오른쪽으로 회전시켜라

 

🧪 예제 

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

 

🔐 문제 풀이

추가 메모리를 사용한 방법. 배열의 rotation은 (i + k) % len(nums) 로 indexing하여 해결할 수 있다.

Runtime complexity : O(N)

Memory complexity : O(N)

 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        N = len(nums)
        tmp = [0] * N
        for i in range(N):
            tmp[(i+k) % N] = nums[i]
        nums[:] = tmp

 

🌡 Follow up

- in-place를 O(1) extra space으로 해결할 수 있는가?