문제 개요
주어진 배열을 특정 규칙에 따라 재배열하는 문제를 살펴보겠습니다. 재배열된 배열의 첫 번째 요소는 최솟값, 두 번째 요소는 최댓값, 세 번째 요소는 두 번째로 작은 값, 네 번째 요소는 두 번째로 큰 값이 되어야 하며, 이후에도 같은 패턴이 반복되어야 합니다. 즉, 작은 값과 큰 값이 번갈아 나타나는 형태로 배열을 정렬하는 것이 목표입니다.
입력 : arr[ ] = { 13, 34, 30, 56, 78, 3 }
출력 : { 3, 78, 13, 56, 34, 30 }
설명 : 배열이 { 1번째 최솟값, 1번째 최댓값, 2번째 최솟값, 2번째 최댓값, 3번째 최솟값, 3번째 최댓값 } 순서로 재배열됩니다.
입력 : arr[ ] = { 2, 4, 6, 8, 11, 13, 15 }
출력 : { 2, 15, 4, 13, 6, 11, 8 }해결 접근 방법
이 문제는 두 개의 포인터 변수 x와 y를 사용하면 효율적으로 해결할 수 있습니다. x는 최솟값 쪽을, y는 최댓값 쪽을 가리키는 역할을 합니다.
다만 이 방법을 적용하려면 먼저 배열이 오름차순으로 정렬되어 있어야 합니다. 따라서 다음과 같은 순서로 진행합니다.
- 원본 배열을 먼저 오름차순으로 정렬합니다.
- 재배열된 결과를 저장할 같은 크기의 새로운 빈 배열을 생성합니다.
- 배열을 순회하면서 인덱스가 짝수일 때는 arr[x] 값을 새 배열에 추가하고 x를 1 증가시킵니다.
- 인덱스가 홀수일 때는 arr[y] 값을 새 배열에 추가하고 y를 1 감소시킵니다.
- x가 y보다 커질 때까지 위 과정을 반복합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main () {
int arr[] = { 2, 4, 6, 8, 11, 13, 15 };
int n = sizeof (arr) / sizeof (arr[0]);
// 재배열된 배열을 저장할 새로운 배열 생성
int reordered_array[n];
// 원본 배열 정렬
sort(arr, arr + n);
// 최솟값 인덱스와 최댓값 인덱스를 가리키는 변수 초기화
int x = 0, y = n - 1;
int i = 0;
// x가 y보다 작거나 같을 때까지 반복
while (x <= y) {
// i가 짝수면 최솟값 인덱스의 요소 저장
if (i % 2 == 0) {
reordered_array[i] = arr[x];
x++;
}
// i가 홀수면 최댓값 인덱스의 요소 저장
else {
reordered_array[i] = arr[y];
y--;
}
i++;
}
// 재배열된 배열 출력
for (int i = 0; i < n; i++)
cout << reordered_array[i] << " ";
// 또는 원본 배열을 직접 갱신할 수도 있습니다.
// for (int i = 0; i < n; i++)
// arr[i] = reordered_array[i];
return 0;
}실행 결과
2 15 4 13 6 11 8
코드 동작 원리
- 변수를 x = 0, y = 배열 길이(n) - 1로 초기화합니다.
while (x <= y)조건으로 x가 y보다 커질 때까지 배열을 순회합니다.- 인덱스 i가 짝수일 경우, 정렬된 배열의 앞쪽(arr[x]) 요소를 결과 배열에 추가하고 x를 1 증가시킵니다.
- 인덱스 i가 홀수일 경우, 뒤쪽(arr[y]) 요소를 결과 배열에 추가하고 y를 1 감소시킵니다.
- 최종적으로 재배열된 배열이
reordered_array[]에 저장됩니다.
마무리
이 글에서는 주어진 배열을 최솟값, 최댓값, 두 번째 최솟값, 두 번째 최댓값 순으로 교차 재배열하는 해결 방법을 살펴보고, 이를 C++ 프로그램으로 구현했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)이며, 공간 복잡도는 결과를 저장할 배열만큼 O(n)입니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.