C++ 코딩테스트 강좌, 절댓값 힙 구현하기

이번 강좌에서는 절댓값 힙을 구현하는 알고리즘 문제를 다루고자 합니다. 이 문제는 C++ 프로그래밍에서 자주 출제되는 유형 중 하나로, 우선순위 큐(Priority Queue)를 사용하여 해결할 수 있습니다. 절댓값 힙은 특정 숫자의 절댓값을 기준으로 정렬하는 자료구조입니다.

문제 설명

절댓값 힙은 다음과 같은 연산을 지원합니다:

정수 x를 힙에 삽입합니다.
가장 작은 절댓값을 가진 정수를 힙에서 제거하고 반환합니다. 만약 절댓값이 같은 수가 여러 개일 경우, 더 작은 값을 반환합니다. 만약 힙이 비어있다면 0을 반환합니다.

입력

첫 번째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어집니다. 다음 N개의 줄에는 실행할 연산이 주어집니다. 연산은 다음 두 가지로 나뉩니다:

삽입: 0 x (−10⁹ ≤ x ≤ 10⁹) 형태로 주어지며, 절댓값 힙에 x를 삽입합니다.
삭제: 0 형태로 주어지며, 절댓값 힙에서 가장 작은 절댓값을 가진 정수를 제거하고 반환합니다.

출력

삭제 연산의 결과를 한 줄에 하나씩 출력합니다.

예제 입력

예제 출력

문제 접근

이 문제를 해결하기 위해 우선순위 큐를 사용할 것입니다. C++ 표준 라이브러리에서는 std::priority_queue를 제공하는데, 기본적으로 최대 힙으로 작동합니다. 하지만 우리는 절댓값을 기준으로 최소 힙을 만들어야 합니다. 따라서 std::priority_queue를 커스터마이징하여 이를 구현할 것입니다.

힙 구현

절댓값 힙을 구현하기 위해 다음과 같은 비교 함수를 정의할 것입니다:

struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // 절댓값이 같으면 더 작은 값을 선택
        }
        return abs(a) > abs(b); // 절댓값 기준으로 선택
    }
};

위와 같은 비교 함수를 기준으로 우선순위 큐를 정의하고, 삽입 연산 및 삭제 연산을 수행할 수 있습니다.

C++ 코드 구현

#include 
#include 
#include 
#include 

using namespace std;

// 비교 연산자 정의
struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // 절댓값이 같으면 더 작은 값을 선택
        }
        return abs(a) > abs(b); // 절댓값을 기준으로 선택
    }
};

int main() {
    int N;
    cin >> N;

    priority_queue, Compare> pq; // 커스터마이징된 우선순위 큐
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            // 삭제 연산
            if (pq.empty()) {
                cout << 0 << endl; // 비어있을 경우 0 출력
            } else {
                cout << pq.top() << endl; // 절댓값 힙에서 가장 작은 값을 출력
                pq.pop(); // 힙에서 삭제
            }
        } else {
            // 삽입 연산
            pq.push(x); // 힙에 값 추가
        }
    }

    return 0;
}

코드 설명

위 C++ 코드는 절댓값 힙을 구현합니다:

priority_queue에서 Compare 구조체를 사용하여 우선순위를 설정하고 있습니다.
main 함수 내에서 입력을 읽고, 0 입력 시에는 힙에서 데이터를 삭제하고 출력하며, 다른 숫자는 힙에 삽입합니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 다음과 같습니다:

삽입 연산: O(log N)
삭제 연산: O(log N)

따라서 총 N개의 연산을 수행할 경우, 전체 시간 복잡도는 O(N log N)입니다.

결론

이번 강좌에서는 C++로 절댓값 힙을 구현하는 방법을 배우고, 우선순위 큐를 활용하여 효율적으로 데이터를 관리하는 방법을 알아보았습니다. 이 문제는 코딩 테스트에서 중요한 개념 중 하나이므로, 연습을 통해 이해를 깊이 있는 것으로 발전시키기를 바랍니다.