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

백준 문제 풀이: 1927 [최소 힙]

---

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

문제 설명:

주어진 명령에 따라 최소 힙을 구성하고 동작을 수행하세요. 명령은 다음과 같습니다:

• 숫자 `x`가 주어질 경우, 이를 최소 힙에 삽입합니다.
• 숫자 `0`이 주어질 경우, 최소 힙에서 가장 작은 값을 출력하고 제거합니다. 만약 힙이 비어 있다면 `0`을 출력합니다.

입력 조건:

• 첫째 줄에 명령의 개수 `n`이 주어집니다. (1 ≤ n ≤ 100,000)
• 다음 `n`개의 줄에는 정수 `x`가 주어집니다. (0 ≤ x ≤ 2³¹ - 1)

출력 조건:

• 입력된 명령에 따라 결과를 출력합니다.

---

문제 해결 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    priority_queue<int, vector<int>, greater<int>> q; // 최소 힙 선언
    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x == 0) {
            // 힙이 비어 있으면 0 출력, 아니면 최솟값 출력
            if (q.empty()) {
                cout << 0 << '\n';
            } else {
                cout << q.top() << '\n';
                q.pop();
            }
        } else {
            q.push(x); // 최소 힙에 삽입
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 `priority_queue`를 사용하여 최소 힙을 구현하고 명령을 처리합니다.

• 입력 처리:
  • 입력된 숫자가 `0`이면 힙에서 최솟값을 출력하고 제거합니다.
  • 숫자가 `0`이 아니면 힙에 삽입합니다.
• 최소 힙 구현:
  • `priority_queue<int, vector, greater>`를 사용하여 최소 힙을 생성합니다.
• 명령 처리:
  • 힙이 비어 있는 경우에는 `0`을 출력합니다.
  • 힙이 비어 있지 않으면 `q.top()`으로 최솟값을 출력하고 `q.pop()`으로 제거합니다.

시간 복잡도 분석:

• 삽입 및 삭제 연산: O(log n).
• 명령 처리: O(n log n).

효율적으로 처리 가능합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
9
0
12345678
1
2
0
0
0
0
32

출력:
0
1
2
12345678
0

명령에 따라 최소 힙이 정확히 동작하며 결과를 출력합니다.

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