배열 (회전은 아니고) rotate는 구현에서 상당히 자주 등장합니다. python에서 배열의 원소들을 손쉽게 rotate 할 수 있는 방법이 없을까요? python deque rotate 함수라면 손쉽게 가능합니다.
함수에 대한 소개와 예제
먼저, 이 함수는 그냥 얼마만큼 원소들을 회전시킬 것인지만 넘겨주면 됩니다.
n은 오른쪽으로 몇 칸 이동 시킬지를 의미합니다. 만약에 n이 음수라면, 절댓값만큼 왼쪽으로 이동하게 됩니다. 이게 무슨 소리인가?
예제 1번 프로그램을 볼게요. deque에 1, 2, 3, 4, 5 순서대로 들어가 있어요. 그러면, 덱에는 아래와 같이 저장이 되어 있을 겁니다.
이 상태에서 de.rotate(-1)을 호출했습니다. -1은 음수이므로, 왼쪽으로 이동합니다. -1의 절댓값은 1이니, 왼쪽으로 1칸만큼 이동하게 됩니다. 그러면, 2와 3, 4, 5는 1칸씩 왼쪽으로 이동합니다.
그러면 1은 어디로 이동할까요? 순환을 생각해 보자고요. 1은 원래 가장 왼쪽에 있었습니다. 가장 왼쪽에서 1칸만큼 왼쪽으로 이동하면, 가장 오른쪽 끝으로 가게 됩니다. 아래 그림과 같습니다.
따라서 5번째 줄 print 문에서는 2, 3, 4, 5, 1이 출력되게 됩니다. 이제, de.rotate(1)을 호출했습니다. 어떻게 될까요? 1은 양수이므로, 오른쪽으로 1칸 이동하게 됩니다.
2, 3, 4, 5, 1을 오른쪽으로 1칸 이동해 봅시다. 2, 3, 4, 5는 어디로 이동할 지 예측하는 것이 쉽습니다. 문제는 1입니다. 1이 원래 맨 오른쪽 끝에 있었기 때문입니다. 마찬가지로 순환을 생각해 봅시다. 오른쪽 끝에서 1칸 이동하면 가장 왼쪽이 됩니다.
따라서, rotate(1)을 호출한 후에는 de에는 1, 2, 3, 4, 5 순서대로 저장되게 됩니다. 여기까지 정리해 봅시다. de에 들어 있는 원소의 개수가 S라고 하겠습니다. 0-base index로 계산합시다. i번째에 있는 원소가 rotate(x)를 호출 후에 어느 위치로 이동할까요?
- x가 양수인 경우, (i + x) mod S 번째 위치로 이동합니다.
- x가 음수인 경우, (i + S – (-x)%S) mod S 번째 위치로 이동합니다.
예를 들어, S가 5이고, x가 -11인 경우, 0번째에 있는 원소는 (0 + 5 – (-11)%5) mod 5 = 4번째 원소로 이동하게 됩니다.
예제 1번 프로그램의 결과는 위와 같습니다.
python deque rotate complexity
그러면 해당 함수의 시간 복잡도는 어떻게 될까요?
위 프로그램은 중간 정도의 거리를 회전시킵니다. 총 50만개의 원소가 있는데, 25만의 거리만큼 회전시키는 것을 볼 수 있지요. 시간이 어떻게 나올까요?
6.3초가 걸렸습니다. 이를 ns 단위로 바꾸면, 63억 ns만큼 걸렸습니다. 이는, 중간 정도의 거리만큼 회전시킬 때 상당히 비효율적으로 동작했다는 의미입니다.
그러면 이 경우는 어떨까요? 위 프로그램은 1칸씩 회전시킵니다.
아까와는 다르게 200만 ns만에 수행이 됩니다. 이제, rotate에 499999를 넣으면 어떻게 동작할까요? 빨라질까요? 느려질까요?
역시 효율적으로 동작합니다. 이는 499999칸 오른쪽으로 회전시키는 것이 1칸 왼쪽으로 회전시키는 것과 같기 때문입니다. 500001칸 오른쪽으로 회전시키는 건 어떨까요? 이는 1칸 오른쪽으로 회전시키는 것과 같지요.
따라서, 1칸을 오른쪽으로 회전시키는 것이나 1+sz칸을 오른쪽으로 회전시키는 것이나, 1+2sz칸을 오른쪽으로 회전시키는 것이나 같다고 볼 수 있어요. 이런 최적화를 안 해 놓았을 리는 없겠지요.
따라서 시간 복잡도 그래프를 그려보면 위와 같습니다. 주기 함수라고 보시면 되겠습니다. x는 rotate에 들어간 1번째 인자입니다. deque의 크기가 sz라고 한다면, 정말 최악의 경우, O(sz/2) = O(sz) 만큼의 복잡도를 가질 수 있다는 의미입니다. 하지만, 1칸 왼쪽 이동이나 1칸 오른쪽 이동 등은, O(1)만에 수행됩니다.