이 문제에서는 하나의 배열이 주어지고, 반전(reversal) 알고리즘을 이용해 배열을 d개의 요소만큼 회전해야 합니다. 예시는 다음과 같습니다.
입력 : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2 출력 : arr[] = [3, 4, 5, 6, 7, 1, 2] 설명 : 배열을 d = 2만큼 회전해야 하며, 핵심은 이 작업을 반전 기법을 사용해서 수행하는 것입니다.
반전 기법으로 배열을 회전하는 과정을 몇 차례 계산해 보면 다음과 같은 결론에 도달할 수 있습니다.
- 첫 번째 단계: 배열의 앞쪽 d개 요소를 반전합니다.
- 두 번째 단계: 나머지 요소들을 반전합니다.
- 세 번째 단계: 배열 전체를 반전합니다.
이 세 가지 단계를 순서대로 적용하면 원하는 만큼 회전된 배열을 얻을 수 있습니다.
문제 해결 접근 방식
먼저 배열의 특정 구간을 반전하는 함수를 만듭니다. 그다음 위에서 정리한 세 단계를 순서대로 적용하면 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void reverseArray(int arr[], int start, int end) { // 반전 알고리즘
while (start < end) { // start가 end와 같아지면 루프 종료
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
return ;
}
void Rotate(int arr[], int d, int n) { // 회전 함수
if (d == 0) // 회전이 필요 없는 경우
return;
d = d % n; // d가 n과 같아지면 배열은 원래 상태로 돌아옴
reverseArray(arr, 0, d - 1); // 앞쪽 d개 요소 반전
reverseArray(arr, d, n - 1); // 나머지 요소 반전
reverseArray(arr, 0, n - 1); // 배열 전체 반전
return ;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // 주어진 배열
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
int d = 2;
Rotate(arr, d, n);
for(int i = 0; i < n; i++) // 배열 출력
cout << arr[i] << " ";
cout << "\n";
return 0;
}실행 결과
3 4 5 6 7 1 2
코드 설명
위 접근 방식에서는 먼저 반전 함수를 생성합니다. 이 함수는 배열, 시작 인덱스, 끝 인덱스라는 세 개의 매개변수를 받아 해당 구간의 요소들을 서로 교환하며 반전시킵니다.
이후 Rotate 함수에서는 앞서 설계한 알고리즘대로 다음 작업을 수행합니다.
- 첫 번째로 앞쪽 d개의 요소를 반전합니다.
- 두 번째로 나머지 요소들을 반전합니다.
- 마지막으로 배열 전체를 반전합니다.
그 결과 배열이 정확히 d만큼 회전됩니다. 여기서 d = d % n 연산을 수행하는 이유는, 길이가 n인 배열을 n번 회전하면 원래 상태와 동일해지기 때문입니다. 따라서 d가 n보다 큰 경우에도 불필요한 연산을 줄이고 올바른 결과를 얻으려면 나머지 연산이 필요합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 배열 전체를 최대 두 번 순회하므로 선형 시간이 소요됩니다.
- 공간 복잡도: O(1) — 임시 변수만 사용하므로 추가 메모리가 거의 필요하지 않습니다.
마무리
이 글에서는 반전 알고리즘을 활용해 배열을 회전하는 문제를 해결했습니다. C++로 작성된 전체 프로그램과 함께 문제 해결의 완전한 접근 방식까지 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 방법은 추가 배열 없이 제자리(in-place)에서 회전을 수행할 수 있어 실무에서도 유용하게 활용됩니다. 이 글이 도움이 되기를 바랍니다.