이원 정렬의 개념

알고리즘 문제 풀이 과정에서 두 가지 이상의 데이터를 묶어서 정렬해야 하는 상황을 자주 접하게 됩니다. 예를 들어, 길이가 $n$인 두 수열 $A = \{a_1, a_2, \dots, a_n\}$과 $B = \{b_1, b_2, \dots, b_n\}$이 주어졌을 때, 먼저 $a_i$를 기준으로 오름차순 정렬하고, $a_i$ 값이 같다면 $b_i$를 기준으로 다시 오름차순 정렬하는 방식입니다. 이를 C++에서 구현하는 다양한 방법을 정리합니다.

구조체와 std::sort 활용

가장 범용적인 방법은 데이터를 구조체(struct)로 묶고 std::sort 함수를 사용하는 것입니다. 비교 로직을 정의하는 방식에 따라 크게 세 가지로 나뉩니다.

1. 외부 비교 함수 정의

별도의 비교 함수를 만들어 std::sort의 세 번째 인자로 전달합니다.

struct Element {
    int primary;
    int secondary;
};

bool compareElements(const Element& lhs, const Element& rhs) {
    if (lhs.primary == rhs.primary) {
        return lhs.secondary < rhs.secondary;
    }
    return lhs.primary < rhs.primary;
}

// 사용 예시
Element arr[MAX_N];
std::sort(arr, arr + n, compareElements);

2. 연산자 오버로딩 (Operator Overloading)

구조체 내부에 < 연산자를 직접 정의하여 std::sort가 기본적으로 이 규칙을 사용하도록 합니다.

struct Point {
    int x, y;

    // 상수 멤버 함수로 정의
    bool operator<(const Point& other) const {
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }
};

Point pts[MAX_N];
std::sort(pts, pts + n);

std::pair 활용

std::pair는 이미 내부적으로 first를 우선 비교하고, 값이 같을 경우 second를 비교하도록 < 연산자가 구현되어 있습니다. 별도의 구조체 정의 없이 간단하게 이원 정렬을 수행할 수 있습니다.

#include <vector>
#include <algorithm>
#include <utility>

std::vector<std::pair<int, int>> vec;
for (int i = 0; i < n; ++i) {
    int u, v;
    std::cin >> u >> v;
    vec.push_back({u, v});
}

std::sort(vec.begin(), vec.end());

STL 컨테이너별 정렬 특성

데이터의 저장 방식과 목적에 따라 정렬을 유지하는 컨테이너를 선택할 수 있습니다.

std::priority_queue (우선순위 큐)

데이터를 삽입할 때마다 정렬된 상태를 유지하지만, 가장 큰 값(기본 설정)부터 접근 가능하며 임의 접근은 불가능합니다.

// std::pair를 사용하면 자동으로 first, second 순으로 우선순위 결정
std::priority_queue<std::pair<int, int>> pq;

pq.push({10, 20});
pq.push({10, 5});

// pq.top()은 {10, 20}을 반환

std::set / std::multiset

균형 이진 탐색 트리(Red-Black Tree) 기반의 컨테이너로, 삽입과 동시에 정렬이 이루어집니다. std::set은 중복을 제거하며, std::multiset은 중복을 허용합니다.

struct Node {
    int val1, val2;
    bool operator<(const Node& o) const {
        if (val1 == o.val1) return val2 < o.val2;
        return val1 < o.val1;
    }
};

std::set<Node> s;
s.insert({1, 5});
s.insert({1, 2});

for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << it->val1 << " " << it->val2 << std::endl;
}

시간 복잡도 분석

위에서 소개한 std::sort, std::priority_queue, std::set을 이용한 방식은 모두 데이터 $N$개에 대해 $O(N \log N)$의 시간 복잡도를 가집니다. 다만, 데이터의 동적 추가가 빈번하다면 set이나 priority_queue가 유리하고, 한 번에 모든 데이터를 받아 정렬한다면 std::vector와 std::sort를 조합하는 방식이 메모리와 속도 측면에서 가장 효율적입니다.