C++ 흔들기 정렬 II(Wiggle Sort II)란?
정렬되지 않은 배열 nums가 주어졌을 때, nums[0] < nums[1] > nums[2] < nums[3] ...처럼 값이 오르내리기를 반복하는 파도 모양(교차 순서)이 되도록 재배열하는 문제입니다.
예를 들어 입력이 [1,5,1,1,6,4]라면, 결과는 [1,6,1,5,1,4]가 됩니다. 즉, 짝수 번째 인덱스의 값은 양쪽 이웃보다 작고, 홀수 번째 인덱스의 값은 양쪽 이웃보다 커야 합니다.
접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다.
원본 배열을 복사한 배열 x를 만든 뒤 오름차순으로 정렬합니다.
정렬된 배열의 앞쪽 절반(작은 값들)을 끝에서부터 거꾸로 짝수 인덱스(0, 2, 4, ...)에 채웁니다.
정렬된 배열의 뒤쪽 절반(큰 값들)을 끝에서부터 거꾸로 홀수 인덱스(1, 3, 5, ...)에 채웁니다.
값을 역순으로 배치하면 중복된 원소들이 서로 인접한 위치에 놓이는 것을 방지할 수 있어, 중복 값이 포함된 입력에서도 올바른 교차 순서를 보장합니다.
단계별 알고리즘
nums와 동일한 요소를 가진 배열 x를 생성합니다.
x 배열을 정렬합니다.
i := x의 크기 − 1, j := (x의 크기 − 1) / 2, n := nums의 크기로 초기화합니다.
l을 0부터 n−1까지 2씩 증가시키며 반복합니다.
nums[l] := x[j]
j를 1 감소시킵니다.
l을 1부터 n−1까지 2씩 증가시키며 반복합니다.
nums[l] := x[i]
i를 1 감소시킵니다.
구현 예제
아래 C++ 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector <int> x(nums);
sort(x.begin(), x.end());
int i = x.size() - 1 ;
int j = (x.size() - 1)/2;
int n = nums.size();
for(int l = 0; l < n; l +=2){
nums[l] = x[j--];
}
for(int l = 1; l < n; l +=2){
nums[l] = x[i--];
}
}
};
main(){
vector<int> v = {1,5,1,1,6,4};
Solution ob;
(ob.wiggleSort(v));
print_vector(v);
}입력
[1,5,1,1,6,4]
출력
[1, 6, 1, 5, 1, 4]
복잡도 분석
배열을 한 번 정렬해야 하므로 시간 복잡도는 O(n log n)이며, 복사본 배열 x를 위해 O(n)의 추가 공간이 필요합니다.