회전된 배열을 뒤집어야 하는 상황에서는 반전 알고리즘(Reversal Algorithm)이 매우 효율적인 해결 방법이 됩니다. 이 알고리즘은 리스트를 직접 순회하면서 요소의 위치를 서로 교환하는 방식으로 동작하며, 추가 메모리 없이 제자리(in-place)에서 배열을 조작할 수 있다는 장점이 있습니다.
핵심 아이디어는 간단합니다. 왼쪽으로 k칸 회전하고 싶다면 다음 세 단계의 반전 연산만 수행하면 됩니다.
- 처음부터 k-1번째까지의 부분 배열을 반전
- k번째부터 마지막까지의 부분 배열을 반전
- 전체 배열을 한 번 더 반전
예제 코드
def reverse_list(my_list, begin, end):
while (begin < end):
temp = my_list[begin]
my_list[begin] = my_list[end]
my_list[end] = temp
begin += 1
end = end - 1
def left_rotate(my_list, to_rotate):
n = len(my_list)
reverse_list(my_list, 0, to_rotate - 1)
reverse_list(my_list, to_rotate, n - 1)
reverse_list(my_list, 0, n - 1)
def print_it(my_list):
for i in range(0, len(my_list)):
print(my_list[i])
my_list = [34, 42, 56, 78, 9, 0, 23]
print("The list is :")
print(my_list)
print("The left_rotate method is being called")
left_rotate(my_list, 3)
print("The list after rotation is : ")
print_it(my_list)실행 결과
The list is : [34, 42, 56, 78, 9, 0, 23] The left_rotate method is being called The list after rotation is : 78 9 0 23 34 42 56
코드 설명
- reverse_list 함수: 시작 인덱스(begin)와 끝 인덱스(end)를 받아 해당 범위의 요소들을 양 끝부터 서로 교환하며 리스트를 반전시킵니다. 두 포인터가 만나거나 교차하면 반복이 종료됩니다.
- left_rotate 함수: 리스트의 길이를 구한 뒤, 위에서 설명한 세 단계의 반전 연산을 순서대로 호출하여 지정한 칸 수(to_rotate)만큼 왼쪽 회전을 수행합니다.
- print_it 함수: 리스트의 모든 요소를 콘솔에 한 줄씩 출력하는 보조 함수입니다.
- 예제에서는 [34, 42, 56, 78, 9, 0, 23] 리스트를 정의하고 화면에 출력한 후,
left_rotate메서드를 호출해 3칸 왼쪽으로 회전시킵니다. - 회전이 완료되면 결과가 [78, 9, 0, 23, 34, 42, 56]으로 변경되며, 이를 콘솔에 출력하여 확인할 수 있습니다.
알고리즘의 장점
이 방법은 시간 복잡도가 O(n)이고 공간 복잡도가 O(1)입니다. 즉, 임시 배열을 따로 만들지 않고도 원본 리스트 내에서 직접 요소를 교환하기 때문에 메모리 효율이 뛰어나며, 큰 크기의 배열을 다룰 때 특히 유용합니다.