1.10 배열의 회전

main.py

"""
## 문제 : 1.10 배열의 회전

- 입력으로 정수형 배열과 k 값이 주어지면, 각 요소를 우측으로
k 번 이동 및 회전을 해보자.
- k는 양의 정수 값이다.
- 예를 들어서, nums 배열에 [1, 2, 3, 4] 가 있고, k가 1이라면 요소는 우측으로 1칸씩
이동 및 회전하여 [4, 1, 2, 3] 이 된다.

## 제한사항 :

- 졍수형 배열이다.

## 아이디어 :

1. 리스트의 성질을 이용
- 리스트의 pop_left() 함수와, append() 함수를 이용하여 구현하면 될 것 같다.
- 시간 복잡도 : O(N)
- 공간 복잡도 : O(1)

2. k번 이동할 값을 배열의 크기로 나눈 후 나머지 값만 이동시킨다.

- 여기서 리스트를 사용할 때는 맨 앞의 요소를 추가하거나, 삭제할 때 O(n)의 시간 복잡도를 가지는데 비해서
- deque를 사용하면 O(1) 시간 복잡도로 끝낼 수 있다.
## 구현 :

## 테스트 :
- k가 0일때 원본 배열을 반환한다.
- k가 원본 배열의 길이와 같을 때 원본 배열을 반환한다.
"""
from collections import deque
from typing import Deque
from typing import List


def solve(nums: deque[int], k: int) -> List[int]:
    length = len(nums)
    move = k % length

    for n in range(move):
        t = nums.pop()
        nums.appendleft(t)
    print(nums)


if __name__ == '__main__':
    nums = deque(map(int, input().split()))
    k = int(input())
    solve(nums, k)

def solve(nums: Deque[int], k: int) -> List[int]:
    length = len(nums)
    move = k % length

    nums.rotate(move)
    print(nums)

• rotate() 함수를 지원하여 더욱 간단하게 만들 수 있다.

from typing import List


def rotate(nums: List[int], k: int) -> None:
    for _ in range(k):
        prev = nums[len(nums) - 1]
        for idx in range(len(nums)):
            nums[idx], prev = prev, nums[idx]
    return nums


def rotate1(nums: List[int], k: int) -> None:
    temp = [0] * len(nums)

    for i, v in enumerate(nums):
        temp[(k + i) % len(nums)] = v

    nums[:] = temp


def rotate2(nums: List[int], k: int) -> None:
    count = 0

    for start in range(len(nums)):

        if count >= len(nums):
            break

        current_index = start
        prev_elem = nums[start]

        while True:
            next_index = (current_index + k) % len(nums)
            nums[next_index], prev_elem = prev_elem, nums[next_index]

            current_index = next_index
            count += 1

            if start == current_index:
                break


def rotate3(nums: List[int], k: int) -> None:
    k = k % len(nums)
    nums[:] = nums[::-1]
    nums[0:k] = nums[0:k][::-1]
    nums[k:len(nums)] = nums[k:len(nums)][::-1]

• 배열을 이용해서 풀었어야 하는데, 다음부터는 주의해야겠다.
• 배열의 인덱스를 이용하여 계산하는게 조금은 머리가 아팠지만, 연습을 해야겠다.