[LeetCode] Rotate Array

목차

문제

• 주어진 배열을 k만큼 rotate 시키는 문제입니다. (단, 추가적인 공간을 생성하지 않고 문제를 해결해야 합니다.)
• 예시

  • 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]

  • 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]

문제 풀이

풀이 1 : Brute Force (하나씩 옮기기)

• 풀이
  • 제일 뒤에 있는 값을 제일 앞으로 보내고, 한 칸씩 뒤로 보내는 작업을 반복해서 진행합니다.
  • 단, 이 방법은 시간복잡도가 O(nxk)가 걸리게 됩니다.
• 코드

  • class Solution:
        def rotate(self, nums: List[int], k: int) -> None:
            k %= len(nums)
            
            for i in range(k):
                previous = nums[-1]
                for j in range(len(nums)):
                    nums[j],previous = previous,nums[j] # swap

풀이 2 : Using Reverse

• 풀이
  • 전체를 뒤집고, 앞에 k개를 뒤집은 뒤, 다시 뒷부분에서 n-k 개를 뒤집게 되면 k만큼 rotate 한 값이 됩니다.
  • 예를 들어 1 2 3 4 5 6 7 이 있고, k=3번 rotate를 진행하면 결과는 5 6 7 1 2 3 4 가 나와야 합니다. 
  • 이를 만들기 위해 먼저 전체를 뒤집게 되면 7 6 5 4 3 2 1이 되고, 여기서 앞에 3개를 뒤집게 되면 5 6 7 4 3 2 1이 됩니다. 여기서 마지막으로 뒤에 4개를 뒤집게 되면 5 6 7 1 2 3 4로 원하는 값이 나오게 됩니다.
  • 주의할 점
    • nums = nums[::-1]로 하면 안 됩니다. nums[::-1]을 할 때 새로운 공간을  생성하여 메모리를 추가로 사용하게 됩니다. 따라서 오른쪽에 할당되는 값에는 슬라이싱을 사용하게 되면 모두 추가적인 공간을 할당하는 것입니다.
    • 왼쪽에서 기존 배열에 특정 값을 넣어주는 것은 추가적인 공간을 생성하는 것이 아닙니다.
      • nums[:a] = ~~  → 추가적인 공간 생성 x
      • ~~ = nums[:a]  → 추가적인 공간 생성 o
  • 따라서 뒤집는 코드를 사용할 때 메모리를 사용하지 않으려면 nums = nums[::-1] 이 아닌 swap 방식을 통해 변경해주어야 합니다.
• 코드

  • class Solution:
        def reverse(self,nums,start,end):
            while start<end:
                nums[start],nums[end]= nums[end],nums[start]
                start,end=start+1,end-1
    
        def rotate(self, nums: List[int], k: int) -> None:
            
            n = len(nums)
            k %= len(nums)
            
            self.reverse(nums,0,n-1)
            self.reverse(nums,0,k-1)
            self.reverse(nums,k,n-1)

알게 된 내용

• 리스트 슬라이싱시에 해당 슬라이싱이 = 기준 오른쪽에 있으면 추가적인 메모리 할당을 한 뒤에 새로운 변수에 할당해 주는 것입니다. (단, = 기준 왼쪽에 있으면 기존 리스트 메모리 공간에 특정 값들을 할당하는 것이라서 추가적인 메모리소모가 되지 않습니다.)
• 추가적인 메모리를 사용하지 않고 기존 리스트 뒤집는 방법
  • 
• 추가적인 메모리를 사용하지 않고 기존 리스트를 rotate 하는 방법(리스트를 뒤집는 방법만으로 rotate시키기)
  • 

출처

• https://leetcode.com/explore/learn/card/array-and-string/204/conclusion/1182/