배열 회전 문제란?
배열 A가 주어졌을 때, 이 배열을 오른쪽으로 k칸 회전해야 하는 문제를 생각해 보겠습니다. 예를 들어 배열이 A = [5, 7, 3, 6, 8, 1, 5, 4]이고 k = 3이라면, 최종 결과는 [1, 5, 4, 5, 7, 3, 6, 8]이 됩니다.
회전 과정은 한 칸씩 차례대로 진행되며, 각 단계는 다음과 같습니다.
- 1단계: [4, 5, 7, 3, 6, 8, 1, 5]
- 2단계: [5, 4, 5, 7, 3, 6, 8, 1]
- 3단계: [1, 5, 4, 5, 7, 3, 6, 8]
해결 접근 방법
매번 한 칸씩 옮기면 비효율적이므로, 슬라이싱을 활용하면 한 번의 연산으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 크기를 n이라고 정의합니다.
- k = k mod n으로 계산합니다. 배열을 n번 회전하면 원래 상태로 돌아오므로, k가 n보다 클 경우 불필요한 반복을 제거할 수 있습니다.
- 배열의 뒤쪽 k개 요소(인덱스 n-k부터 끝까지)를 앞으로 가져오고, 나머지 앞부분(인덱스 0부터 n-k-1까지)을 뒤에 붙여 새로운 배열을 만듭니다.
예를 들어 n = 8, k = 3인 경우, 마지막 3개 요소 [1, 5, 4]를 앞에 두고 앞의 5개 요소 [5, 7, 3, 6, 8]을 뒤에 이어 붙이면 [1, 5, 4, 5, 7, 3, 6, 8]이 됩니다.
구현 코드
아래 코드는 Python의 슬라이싱 기능을 사용해 배열을 제자리(in-place)에서 회전하는 방법을 보여줍니다. nums[:] 슬라이스에 대입하면 함수 외부의 원본 리스트도 함께 변경됩니다.
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: None Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
nums[:] = nums[n-k:] + nums[:n-k]
nums = [5,7,3,6,8,1,5,4]
ob1 = Solution()
ob1.rotate(nums, 3)
print(nums)입력
nums = [5,7,3,6,8,1,5,4] k = 3
출력
[1,5,4,5,7,3,6,8]
마무리
이 방법의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 슬라이싱 없이 두 포인터를 이용해 뒤집는 방식으로 구현하면 공간 복잡도를 O(1)로 줄일 수 있으니, 참고로 알아두면 좋습니다.