C++로 구현하는 최댓값·최솟값 교차 정렬 알고리즘

문제 개요

정수로 이루어진 리스트 nums가 주어졌을 때, 아래 규칙에 따라 리스트를 재정렬해야 합니다.

첫 번째 요소는 최댓값
두 번째 요소는 최솟값
세 번째 요소는 두 번째로 큰 값
네 번째 요소는 두 번째로 작은 값

이후에도 같은 방식으로 큰 값과 작은 값이 번갈아 배치됩니다.

예를 들어 입력이 [6, 3, 10, 4]라면, 출력은 [10, 3, 6, 4]가 됩니다. 즉, 가장 큰 값(10), 가장 작은 값(3), 두 번째로 큰 값(6), 두 번째로 작은 값(4) 순서로 정렬되는 것입니다.

해결 접근 방법

이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 배열을 먼저 오름차순으로 정렬한 뒤, 양쪽 끝에서부터 값을 하나씩 번갈아 가져오면 원하는 순서를 만들 수 있습니다.

구체적인 해결 단계는 다음과 같습니다.

결과를 저장할 배열 ret을 정의합니다.
배열 nums를 오름차순으로 정렬합니다.
j를 마지막 인덱스(nums.size() - 1)로, i를 0으로 초기화합니다.
i <= j인 동안 다음을 반복합니다.
- ret의 끝에 nums[j](큰 값)를 추가한 뒤 j를 1 감소시킵니다.
- 여전히 i <= j라면 ret의 끝에 nums[i](작은 값)를 추가한 뒤 i를 1 증가시킵니다.
ret을 반환합니다.

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:
    vector<int> solve(vector<int> & nums) {
        vector<int> ret;
        sort(nums.begin(), nums.end());
        int j = nums.size() - 1;
        int i = 0;
        while (i <= j) {
            ret.push_back(nums[j]);
            j--;
            if (i <= j) {
                ret.push_back(nums[i]);
                i++;
            }
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<int> v = {6,3,10,4};
    print_vector(ob.solve(v));
}

입력

{6,3,10,4}

출력

[10, 3, 6, 4]

동작 원리 및 복잡도 분석

이 알고리즘의 핵심은 정렬된 배열에서 가장 큰 값과 가장 작은 값을 양 끝에서부터 번갈아 꺼내는 것입니다. 정렬 후 배열이 [3, 4, 6, 10]이 되면, 뒤쪽 포인터 j가 10 → 6을, 앞쪽 포인터 i가 3 → 4를 차례로 추가하여 최종적으로 [10, 3, 6, 4]가 완성됩니다.

시간 복잡도: O(n log n) — 정렬 단계가 전체 성능을 지배합니다.
공간 복잡도: O(n) — 결과를 저장할 새로운 배열이 필요합니다.

요소 개수가 홀수인 경우에도 i == j 시점에 중앙값이 한 번만 추가되므로, 코드 수정 없이 올바르게 동작한다는 점도 장점입니다.