n개의 요소로 이루어진 배열이 있다고 가정해 보겠습니다. 우리가 해야 할 작업은 배열에 담긴 요소들의 순서를 실제로 뒤집은 뒤 그 결과를 화면에 출력하는 것입니다. 여기서 중요한 점은 단순히 역순으로 출력하는 것이 아니라, 배열 내부의 요소 자체를 제자리(in-place)에서 뒤집어야 한다는 것입니다.
예를 들어 입력이 다음과 같다면,
- n = 6
- arr = [9, 8, 7, 2, 4, 3]
출력 결과는 [3, 4, 2, 7, 8, 9]가 됩니다.
해결 접근 방법
배열을 뒤집는 가장 기본적인 방법은 양쪽 끝에서부터 서로 만나며 요소를 교환(swap)하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 인덱스
i를 0부터n/2미만까지 1씩 증가시키며 반복합니다.temp := arr[i]— 현재 요소를 임시 변수에 저장합니다.arr[i] := arr[n - i - 1]— 끝에서i번째 떨어진 요소를 앞쪽에 대입합니다.arr[n - i - 1] := temp— 저장해 둔 값을 뒤쪽 위치에 대입하여 교환을 완성합니다.
- 인덱스
i를 0부터n미만까지 반복하면서 각 요소arr[i]를 차례대로 출력합니다.
이 방식은 배열의 절반만 순회하면 되기 때문에 시간 복잡도가 O(n/2), 즉 O(n)이며, 추가 메모리 없이 임시 변수 하나만 사용하므로 공간 복잡도는 O(1)입니다.
예제 코드
아래는 위 알고리즘을 C 언어로 구현한 예제입니다.
#include <stdio.h>
#include <stdlib.h>
#define n 6
int main(){
int arr[n] = {9, 8, 7, 2, 4, 3};
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++){
printf("%d,", arr[i]);
}
}입력
6, 9, 8, 7, 2, 4, 3
출력
3,4,2,7,8,9,
코드 설명
매크로 #define n 6으로 배열의 크기를 정의하고, 첫 번째 반복문에서 배열의 절반(n/2)까지만 순회하면서 arr[i]와 arr[n-i-1]의 값을 임시 변수 temp를 이용해 서로 맞바꿉니다. 두 번째 반복문에서는 뒤집힌 배열 전체를 콤마(,)로 구분하여 출력합니다. 실행 결과 배열이 완전히 역순으로 정렬된 것을 확인할 수 있습니다.