Skip to main content

Rotate Array

Rotate Array​

정수 배열 nums가 주어지면 배열을 k 단계만큼 오른쪽으로 회전합니다. 여기서 k는 음수가 아닙니다.

입출력 예제​

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]

나의 풀이​

from collection import deque

class Solution(object):
  def rotate(self, nums, k):
    # 시간 복잡도 향상을 위해 데크 자료형 사용
    dq = deque(nums)

    # k가 0보다 클 경우 앞에 0을 추가 (반복문 순회 전 최초)
    if k > 0:
      dq.appendleft(0)

    # k번 만큼 맨 앞 요소와 맨 뒤 요소를 스위칭해야 하므로 k번 만큼 반복
    for i in range(0, k):
      dq[0], dq[-1] = dq[-1], dq[0] # 맨 앞 요소와 맨 뒤 요소를 스위칭
      dq.pop() # 맨 뒤 0 제거

      if i != k - 1: # 반복문 내 마지막에는 0을 추가하면 안되므로 조건문 추가
        dq.appendleft(0)

    # 문제 조건에 맞춰 배열 nums의 요소를 변경해야만 하므로 데크자료형의 모든 요소를 nums 배열에 다시 저장
    for i in range(len(nums)):
      nums[i] = dq[i]

    return nums

풀이 과정​

맨 앞에 0을 추가하고 맨 앞 요소인 0과 맨 마지막 요소인 숫자를 바꾸고 바꾼 뒤에 맨 마지막 요소에 0을 제거하는 과정을 반복하여 결과를 도출하게 됩니다. 아래는 첫 번째 입출력 예제를 사용해 로직 처리 과정 중 deque의 요소 변화입니다.

[1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7] # 맨 앞에 0 추가
[7, 1, 2, 3, 4, 5, 6, 0] # 맨 앞 요소와 맨 뒤 요소를 스위칭
[7, 1, 2, 3, 4, 5, 6] # 맨 마지막 요소 0 제거
-------------------------------------
[0, 7, 1, 2, 3, 4, 5, 6] # 맨 앞에 0 추가
[6, 7, 1, 2, 3, 4, 5, 0] # 맨 앞 요소와 맨 뒤 요소를 스위칭
[6, 7, 1, 2, 3, 4, 5] # 맨 마지막 요소 0 제거
-------------------------------------
[0, 6, 7, 1, 2, 3, 4, 5] # 맨 앞에 0 추가
[5, 6, 7, 1, 2, 3, 4, 0] # 맨 앞 요소와 맨 뒤 요소를 스위칭
[5, 6, 7, 1, 2, 3, 4] # 맨 마지막 요소 0 제거

위 코드는 Runtime 220ms (5.78%)이고 Memory 25.33MB (5.76%)로 현재까지 작성한 코드 중 시간복잡도 및 공간복잡도에서 가장 최악의 경우를 보여줬습니다.

런타임이 최적화된 코드 (0.06% / 123ms)​

class Solution(object):
  def rotate(self, nums, k):
    si = len(nums) - (k % len(nums))
    nums[:] = nums[si:] + nums[0:si]

위 코드에서는 분할점을 찾아 계산식을 도출하고 분할점을 기준으로 뒤에 있는 요소들을 배열로 묶어 앞으로 보내고 앞에 있는 요소들을 배열로 묶어 뒤로 보내 간단한 코드로 효율적인 코드를 작성한 모습입니다.