백준 11279번 [최대 힙](C++) -yes6686- 티스토리

백준 문제 풀이: 11279 [최대 힙]

---

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

문제 설명:

이 문제는 최대 힙을 구현하는 문제입니다. 최대 힙은 다음과 같은 두 가지 연산을 지원해야 합니다:

• x가 양수일 경우, x를 힙에 추가합니다.
• x가 0일 경우, 힙에서 가장 큰 값을 출력하고 제거합니다. 힙이 비어 있다면 0을 출력합니다.

입력:

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

출력:

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

예시:

입력:
6
0
123
1
2
0
0

출력:
0
123
2

---

문제 해결 코드

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

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

    priority_queue<int> 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는 내부적으로 힙 구조를 사용하여 삽입과 삭제 연산을 효율적으로 처리합니다. 최댓값은 O(1)의 시간복잡도로 접근 가능합니다.
• 구현 세부사항:
  • priority_queue<int>: 기본적으로 내림차순으로 정렬된 최대 힙을 제공합니다.
  • pq.top(): 힙의 최댓값을 반환합니다.
  • pq.pop(): 힙에서 최댓값을 제거합니다.
• 시간 복잡도 분석:
  • push와 pop 연산: O(log n) (n은 힙의 크기)
  • 최댓값 접근: O(1)
  • 총 명령 처리: O(T log n)

---

결과

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

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