[Algorithm] 백준 11279번 : 최대 힙 (C++)

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

11279번: 최대 힙

---

[문제]

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

[입력]

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는)연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다.입력되는 자연수는 2³¹보다 작다.

[출력]

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

[알고리즘 분류]

• 자료 구조
• 우선순위 큐

---

[해설]

이 문제는 우선순위 큐 priority_queue를 사용할 줄 안다면 쉽게 해결할 수 있는 문제였다.
우선순위 큐는 queue와 동일한 라이브러리를 통해 제공되며, 원소가 삽입될 때 이름 그대로 우선순위에 따라 값이 정렬되어 삽입된다는 특징을 가지고 있다.

기본적으로 사용하는 명령어는 일반적인 queue와 동일하므로 이를 가지고 문제를 쉽게 해결할 수 있다.

해당 자료구조는 우선순위에 따라 정렬되어 있으므로 q.top()를 하면 가장 앞에 있는 원소 (가장 큰 값)이 출력되고, q.pop()를 하면 가장 앞에 있는 원소(가장 큰 값)가 삭제된다.

이 두 가지를 잘 이용해 로직을 구성하면 아래와 같이 나타낼 수 있다.

[정답 코드]

#include <bits/stdc++.h>
std::priority_queue<int> q;
int N,x;

int main() {
  scanf("%d",&N);
  while(N--){
    scanf("%d",&x);
    if(x) q.push(x);
    else{
      if(q.empty()) printf("0\n");
      else{
        printf("%d\n",q.top());
        q.pop();
      }
    }
  }
}

[결과]