2 분 소요

Array

문제

문제 링크

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

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]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

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?

    스스로 고민

접근법

  • 배열 nums에 있는 숫자들을 k 횟수만큼 오른쪽으로 돌려준다.
  • 예를 들어 1,2,3,4,5 가 있고 k 가 2면 - > 4,5,1,2,3

    의사코드

  • deque 을 사용해서 k 횟수만큼 앞에 있는걸 때서 뒤에 붙여준다.
  • k 만큼 반복

구현 코드

from collections import deque

class Solution:

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

        for _ in range(k):

            x = nums.pop()

            nums.appendleft(x)
  • deque 을 사용하면 nums 자체를 관리하는게 아니라서 안된다.
  • 직접 nums를 조작해야된다.
class Solution:

    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for _ in range(k):

            x = nums.pop()

            nums.insert(0, x)

시간 복잡도와 공간 복잡도

시간 복잡도

  • 주어진 코드에서 pop()과 insert() 함수는 각각 O(1)의 시간 복잡도를 갖는다. 하지만 이들 함수들이 k번 반복되므로 rotate 함수의 전체 시간 복잡도는 O(k * n)이 된다. 여기서 n은 리스트의 길이를 나타낸다. 따라서 k와 n이 모두 큰 값일 경우, 전체 시간 복잡도는 좋지 않다.

공간 복잡도

  • 주어진 코드에서는 주어진 리스트 nums를 직접 수정하므로, 추가적인 공간이 필요하지 않다. 따라서 공간 복잡도는 O(1) 다.

회고 과정

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n  # To handle cases where k > n
        
        # Reverse the entire list
        def reverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        
        reverse(0, n - 1)           # Reverse the entire list
        reverse(0, k - 1)           # Reverse the first k elements
        reverse(k, n - 1)           # Reverse the remaining elements

지금 코드에서 뭘 개선할 수 있지?

  • 이렇게 하면 세 번의 리스트 반전만 하면 되서 시간 복잡도는 O(n) 으로 만들 수 있다.
  • 단순히 구현만 생각했는데 공부할 수록 코드를 작성할 때 어떻게 구성하고 어떻게 작동될지를 염두하면서 작성해야 될 거 같다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        temp = []
        k = k % len(nums)
        temp = nums[-k:]
        nums[k:] = nums[:-k]
        nums[:k] = temp

시간 복잡도

  • 알고리즘은 세 번의 리스트 조작 연산을 수행한다. temp = nums[-k:]는 O(k), nums[k:] = nums[:-k] 역시 O(n), 그리고 nums[:k] = temp도 O(k)의 시간 복잡도를 갖는다. 총 시간 복잡도는 O(n + k)입니다. 하지만 일반적으로 k는 n보다 작으므로 이 알고리즘의 시간 복잡도는 O(n) 다.

공간 복잡도

  • 알고리즘에서 사용되는 추가적인 공간은 temp 리스트 하나뿐이며, 이 리스트는 최대 k개의 원소를 저장한다. 따라서 공간 복잡도는 O(k) 다.

댓글남기기

참고