[Leet Code풀이] 189. Rotate Array

문제 설명

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

리스트를 k만큼 회전시키는 문제

풀이

접근 방법.

[1,2,3,4,5,6,7]에서 k=3인 경우 단순히 루프를 돌면서 i를 k만큼 옮기면서 이동시키면 된다. 그런데 문제는 아래와 같은 경우다.

123456   k=2

위 경우 k만큼 이동하다보면

123456
  1
    3
5
  1 
    3    

과 같이 k만큼 점프하면서 같은 원소만 도는 경우가 생긴다. 그래서 이를 방지하기 위해서 처음 원소가 도는 시작점을 기록하는 init 변수를 두고 i가 다시 init 변수로 돌아올때 i를 +1하는 방식으로 해결했다.

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        # 배열 길이가 k랑 같으면 nums 리턴
        # 배열 길이가 1이면 그대로 리턴
        if len(nums) == k or len(nums) == 1:
            return nums
        
        i = 0
        init = i
        before = nums[i-(k%len(nums))]
        cnt = 1
        while cnt <= len(nums):
            # 만약 한바퀴 돌고 또 나를 만남. 그런데 아직 남은 원소가 있으면 i + 1함
            if i == init and cnt != 1: 
                i += 1
                init += 1
                before = nums[i-(k%len(nums))]
            temp = nums[i]
            nums[i] = before
            before = temp
            i = (i+k)%len(nums)
            cnt += 1

위 풀이의 시간 복잡도와 공간복잡도는 아래와 같다.

• 시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)

• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.