정렬된 배열이 하나 주어집니다. 이 배열을 최대-최소(max-min) 형태로 재배열해야 합니다. 즉, 첫 번째 요소에는 최댓값, 두 번째 요소에는 최솟값, 세 번째 요소에는 두 번째로 큰 값, 네 번째 요소에는 두 번째로 작은 값을 배치하는 식으로 교차하여 배열하는 것입니다.
입력 : arr[ ] = { 10, 20, 30, 40, 50, 60 }
출력 : { 60, 10, 50, 20, 40, 30 }
설명 : 배열이 { 1번째 최댓값, 1번째 최솟값, 2번째 최댓값, 2번째 최솟값, 3번째 최댓값, 3번째 최솟값 } 형태로 재배열됩니다.
입력 : arr [ ] = { 15, 17, 19, 23, 36, 67, 69 }
출력 : { 69, 15, 67, 17, 36, 19, 23 }문제 해결 접근법
배열을 최대-최소 형태로 재배열하는 대표적인 방법은 바로 투 포인터(Two Pointer) 기법입니다.
투 포인터(Two Pointer) 접근법
먼저 최댓값과 최솟값의 위치를 가리키는 두 개의 변수 min과 max를 선언하고, 재배열된 결과를 저장할 같은 크기의 빈 배열을 하나 생성합니다. 이후 배열을 순회하면서 다음 규칙에 따라 요소를 채웁니다.
- 현재 채우는 위치의 인덱스가 짝수라면
arr[max]값을 결과 배열에 넣고max를 1 감소시킵니다. - 현재 위치의 인덱스가 홀수라면
arr[min]값을 결과 배열에 넣고min을 1 증가시킵니다.
이 과정은 min이 max보다 커질 때까지 반복하면 됩니다. 정렬된 배열을 이미 가지고 있으므로 별도의 비교 없이 양 끝에서부터 교차하며 값을 꺼내오기만 하면 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main () {
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof (arr) / sizeof (arr[0]);
// 재배열된 배열을 저장할 새로운 배열 생성
int final[n];
// 첫 번째 요소와 마지막 요소의 인덱스를 가리키는 변수
int min = 0, max = n - 1;
int count = 0;
// min이 max보다 작거나 같은 동안 배열 순회
for (int i = 0; min <= max; i++) {
// count가 짝수이면 최대 인덱스의 원소를 저장
if (count % 2 == 0) {
final[i] = arr[max];
max--;
}
// count가 홀수이면 최소 인덱스의 원소를 저장
else {
final[i] = arr[min];
min++;
}
count++;
}
// 최종적으로 재배열된 배열 출력
for (int i = 0; i < n; i++)
cout << final[ i ] << " ";
return 0;
}
실행 결과
6 1 5 2 4 3
코드 상세 설명
min은 0으로,max는 배열 길이에서 1을 뺀 값(n - 1)으로 초기화합니다.for (int i = 0; min <= max; i++)루프를 통해min이max보다 커질 때까지 배열을 순회합니다.count가 짝수일 때는 최대 인덱스(max)의 원소를 결과 배열에 추가하고max를 1 감소시킵니다.count가 홀수일 때는 최소 인덱스(min)의 원소를 결과 배열에 추가하고min을 1 증가시킵니다.- 모든 과정이 끝나면 재배열된 결과가
final[ ]배열에 저장되어 출력됩니다.
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 결과를 담을 배열이 필요하므로 공간 복잡도 역시 O(n)입니다.
마무리
이 글에서는 주어진 정렬된 배열을 최대-최소 형태로 재배열하는 문제를 살펴보았습니다. 투 포인터 기법을 활용한 효율적인 풀이 방법을 설명하고, 시간 복잡도 O(n)의 최적화된 솔루션을 C++ 프로그램으로 구현했습니다. 같은 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.