서로 다른 n개의 요소로 이루어진 배열이 있다고 가정해 봅시다. 우리가 해야 할 작업은 배열에 있는 요소들의 순서를 제자리에서(in-place) 뒤집고, 그 결과를 출력하는 것입니다. 여기서 중요한 점은 단순히 역순으로 출력하는 것이 아니라, 실제 배열 내부의 요소 순서 자체를 반대로 바꿔야 한다는 것입니다.
예를 들어 입력이 다음과 같다면,
- n = 9
- arr = [2, 5, 6, 4, 7, 8, 3, 6, 4]
출력 결과는 다음과 같습니다.
[4, 6, 3, 8, 7, 4, 6, 5, 2]
해결 접근 방법
배열을 제자리에서 뒤집으려면 두 포인터(two pointer) 기법을 활용하면 됩니다. 배열의 앞쪽 요소와 뒤쪽 요소를 서로 맞바꾸면서 중앙까지 진행하는 방식입니다. 구체적인 단계는 다음과 같습니다.
- 인덱스 i를 0부터 시작하여 i < n/2 조건을 만족하는 동안 반복합니다.
- 각 반복마다 임시 변수 temp를 사용해 arr[i]와 arr[n - i - 1]의 값을 서로 교환합니다.
- temp := arr[i]
- arr[i] := arr[n - i - 1]
- arr[n - i - 1] := temp
- 교환이 끝나면 인덱스 i를 0부터 n-1까지 순회하며 배열의 모든 요소를 출력합니다.
C++ 구현 예제
아래 코드를 통해 더 쉽게 이해할 수 있습니다.
#include <iostream>
using namespace std;
int main(){
int n = 9;
int arr[n] = {2,5,6,4,7,8,3,6,4};
int temp;
// 배열을 제자리에서 뒤집는 부분
for(int i = 0; i < n/2; i++){
temp = arr[i];
arr[i] = arr[n-i-1];
arr[n-i-1] = temp;
}
// 뒤집힌 배열 출력
for(int i = 0; i < n; i++){
cout << arr[i] << " ";
}
}
입력
9, {2,5,6,4,7,8,3,6,4}출력
4 6 3 8 7 4 6 5 2
동작 원리와 시간 복잡도
이 알고리즘은 배열의 절반(n/2)만큼만 순회하면서 양끝 요소를 교환하기 때문에, 전체 배열을 한 번씩 확인하는 방식보다 효율적입니다. 각 교환 연산은 상수 시간에 수행되므로 전체 시간 복잡도는 O(n)이며, 추가 배열을 사용하지 않고 기존 배열 안에서 직접 값을 바꾸기 때문에 공간 복잡도는 O(1)입니다.
이러한 in-place 방식은 메모리 사용량이 중요한 환경이나 대용량 데이터를 처리할 때 특히 유용하며, C++의 std::reverse 함수도 내부적으로 유사한 원리로 동작합니다.