이번 튜토리얼에서는 C++를 사용해 배열을 지그재그(zig-zag) 형태로 변환하는 프로그램을 살펴보겠습니다.
이 문제에서는 중복 없이 서로 다른 원소들로 구성된 배열이 하나 주어집니다. 우리가 해야 할 작업은 배열의 원소들을 재배열하여, 인접한 두 원소 사이의 크기 관계가 번갈아 나타나도록 만드는 것입니다. 즉, 첫 번째 원소는 두 번째 원소보다 작고, 두 번째 원소는 세 번째 원소보다 커야 하는 식으로 '<'와 '>' 비교가 교대로 성립하는 패턴을 완성해야 합니다.
예를 들어 입력 배열이 {4, 3, 7, 8, 6, 2, 1}이라면, 변환 후에는 3 < 7 > 4 < 8 > 2 < 6 > 1과 같은 지그재그 구조를 갖게 됩니다.
알고리즘 동작 원리
핵심 아이디어는 매우 간단합니다. 불리언(bool) 타입의 플래그 변수 하나를 사용해 현재 위치에서 어떤 크기 관계가 필요한지를 추적하고, 조건이 맞지 않으면 인접한 두 원소를 스왑(swap)하면 됩니다.
- flag = true일 때: 현재 원소가 다음 원소보다 작아야 합니다(arr[i] < arr[i+1]). 조건을 벗어나면 두 원소를 교환합니다.
- flag = false일 때: 현재 원소가 다음 원소보다 커야 합니다(arr[i] > arr[i+1]). 마찬가지로 조건이 맞지 않으면 교환합니다.
- 각 반복이 끝날 때마다 플래그 값을 뒤집어(!flag) 크고 작음이 번갈아 나타나도록 유지합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
// 배열을 지그재그 형태로 변환하는 함수
void convert_zigzag(int arr[], int n) {
// flag는 "현재 원소가 다음 원소보다 작아야 함(true)" 또는
// "커야 함(false)"인지를 나타냅니다.
bool flag = true;
for (int i = 0; i <= n-2; i++) {
if (flag) {
// arr[i] < arr[i+1]이 되어야 하므로,
// 더 큰 경우 두 원소를 교환
if (arr[i] > arr[i+1])
swap(arr[i], arr[i+1]);
} else {
// arr[i] > arr[i+1]이 되어야 하므로,
// 더 작은 경우 두 원소를 교환
if (arr[i] < arr[i+1])
swap(arr[i], arr[i+1]);
}
flag = !flag;
}
}
int main() {
int arr[] = {4, 3, 7, 8, 6, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
convert_zigzag(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
실행 결과
3 7 4 8 2 6 1
출력 결과를 보면 3 < 7 > 4 < 8 > 2 < 6 > 1처럼 원소들이 작고 큰 값으로 번갈아 배치된 것을 확인할 수 있습니다.
시간 복잡도 분석
이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다. 또한 별도의 보조 배열 없이 제자리(in-place)에서 원소 교환만 수행하기 때문에 공간 복잡도 역시 O(1)로 매우 효율적입니다. 정렬 없이도 최소한의 연산으로 지그재그 패턴을 만들 수 있다는 점이 이 방법의 가장 큰 장점입니다.