백준 11286번 [절댓값 힙](C++) -yes6686- 티스토리

백준 문제 풀이: 11286 [절댓값 힙]

---

문제 링크: https://www.acmicpc.net/problem/11286

문제 설명:

이 문제는 절댓값 힙을 구현하는 문제입니다. 절댓값 힙은 다음과 같은 조건을 만족해야 합니다:

• 힙에서 절댓값이 가장 작은 값을 우선으로 합니다.
• 절댓값이 같을 경우, 더 작은 값을 우선으로 합니다.

명령은 다음과 같습니다:

• 입력값 x가 0일 경우, 힙에서 가장 작은 값을 출력하고 제거합니다. 힙이 비어 있다면 0을 출력합니다.
• 입력값 x가 0이 아닐 경우, x를 힙에 추가합니다.

입력:

• 첫 줄에 명령의 개수 T가 주어집니다.
• 다음 T개의 줄에 정수 x가 주어집니다.

출력:

• 각 x = 0 명령에 대해 힙의 가장 작은 값을 출력합니다. 힙이 비어 있으면 0을 출력합니다.

예시:

입력:
8
1
-1
0
0
0
1
1
0

출력:
-1
1
0
1

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

// 사용자 정의 비교 함수 객체
struct cmp {
    bool operator()(int a, int b) {
        // 절댓값 기준 비교
        if (abs(a) == abs(b)) return a > b; // 절댓값이 같으면 더 작은 수가 우선
        return abs(a) > abs(b); // 절댓값이 작은 수가 우선
    }
};

int main() {
    ios_base::sync_with_stdio(false); // 입출력 속도 향상
    cin.tie(NULL); // C와 C++ 입출력 동기화를 해제

    priority_queue<int, vector<int>, cmp> pq; // 절댓값 힙
    int T;
    cin >> T; // 명령 개수 입력

    while (T--) {
        int x;
        cin >> x; // 명령 입력
        if (x == 0) {
            if (pq.empty()) { // 힙이 비어 있는 경우
                cout << 0 << '\n';
            } else {
                cout << pq.top() << '\n'; // 가장 작은 값을 출력
                pq.pop(); // 값 제거
            }
        } else {
            pq.push(x); // x를 힙에 추가
        }
    }

    return 0;
}

---

코드 설명

이 코드는 우선순위 큐(priority_queue)를 활용하여 절댓값 힙을 구현합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘: 우선순위 큐를 사용자 정의 비교 함수와 함께 사용하여 힙의 정렬 기준을 설정합니다. 절댓값 기준으로 정렬되며, 절댓값이 같을 경우 더 작은 값이 우선합니다.
• 구현 세부사항:
  • priority_queue<int, vector<int>, cmp>: 사용자 정의 비교 함수 cmp를 통해 힙의 정렬 방식을 정의합니다.
  • cmp::operator(): 비교 로직을 설정하며, 절댓값과 값을 기준으로 우선순위를 결정합니다.
  • pq.top(): 힙의 최상단 값을 반환합니다.
  • pq.pop(): 최상단 값을 제거합니다.
• 시간 복잡도 분석:
  • push와 pop 연산: O(log n) (n은 힙의 크기)
  • 총 명령 처리: O(T log n)

---

결과

코드는 주어진 입력에 따라 절댓값 힙 연산을 수행하며, 명령이 실행될 때마다 출력 결과를 보여줍니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!