1.5.4 k 위치만큼 배열 회전하기
문제 1-4 주어진 배열을 k번 회전하는 함수를 작성하세요. 예를 들어 배열 [10, 20, 30, 40, 50, 60]을 2번 회전하면 [30, 40, 50, 60, 10, 20]이 됩니다.
해결책 배열의 회전은 두 단계로 구성됩니다.
• 첫 번째 단계에서는 배열을 반으로 나누고 전반부와 후반부를 각각 회전해 뒤집습니다(reverse).
• 두 번째 단계에서 전체 배열을 회전해 한꺼번에 뒤집습니다.
• 1,2,3,4,5,6,7,8,9,10 → 4,3,2,1,10,9,8,7,6,5 → 5,6,7,8,9,10,1,2,3,4
해결책 1-4
void reverseArray(int *a, int n) { for (int i = 0, j = n - 1; i < j; i++, j--) { a[i] ^= a[j] ^= a[i] ^= a[j]; } } void rotateArray2(int *a, int n, int k) { reverseArray(a, k); reverseArray(&a[k], n - k); reverseArray(a, n); }
분석 배열의 첫 번째 회전은 O(n) 시간에 실행되고 두 번째 회전도 O(n) 시간에 실행됩니다. 따라서 이 알고리즘의 총 시간 복잡도는 O(n)입니다.