C++ 위글 정렬(Wiggle Sort): 배열을 지그재그로 재배열하는 O(n) 알고리즘

문제 개요

정렬되지 않은 배열 nums가 주어졌을 때, 이를 제자리(in-place)에서 재배열하여 nums[0] <= nums[1] >= nums[2] <= nums[3] ... 과 같은 지그재그(위글) 패턴을 만들어야 합니다.

예를 들어 입력이 nums = [3,5,2,1,6,4]라면 결과는 [3,5,1,6,2,4]가 됩니다. 물론 조건만 만족한다면 다른 순서의 답도 허용됩니다.

해결 전략

이 문제는 배열을 한 번만 순회하면서 인접한 두 원소의 대소 관계를 확인하는 방식으로 간단히 해결할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.

• n을 nums의 크기로 설정합니다.
• i를 0부터 n - 2까지 1씩 증가시키며 반복합니다.
  • i가 짝수인데 nums[i] > nums[i+1]이 성립하는 경우, 또는 i가 홀수인데 nums[i] > nums[i+1]이 성립하지 않는 경우, 두 원소를 교환(swap)합니다.

핵심 아이디어는 단순합니다. 짝수 인덱스에서는 현재 값이 다음 값보다 작거나 같아야 하고, 홀수 인덱스에서는 현재 값이 다음 값보다 크거나 같아야 합니다. 이 조건을 벗어나면 인접한 두 값을 즉시 맞바꾸는 것입니다. 이렇게 처리하면 이미 지나간 구간의 패턴이 무너지지 않으므로, 순회가 끝나면 전체 배열이 자연스럽게 위글 패턴을 따르게 됩니다.

시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 추가 메모리 없이 제자리에서 해결되는 매우 효율적인 방법입니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void print_vector(vector<T> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n - 1; i++){
            if((i % 2 == 0) == (nums[i] > nums[i + 1])){
                swap(nums[i], nums[i + 1]);
            }
        }
    }
};

int main(){
    vector<int> v = {3,5,2,1,6,4};
    Solution ob;
    ob.wiggleSort(v);
    print_vector(v);
}

코드 설명

조건식 (i % 2 == 0) == (nums[i] > nums[i + 1])은 위 규칙을 하나의 비교로 압축한 것입니다. 두 불리언 값이 일치할 때, 즉 짝수 인덱스에서 내림차순 위반이 발생했거나 홀수 인덱스에서 오름차순 위반이 발생했을 때 스왑이 수행됩니다.

실행 결과

입력

{3,5,2,1,6,4}

출력

[3, 5, 1, 6, 2, 4]

결과 배열은 3 <= 5 >= 1 <= 6 >= 2 <= 4를 만족하므로 올바른 위글 정렬입니다.