오늘을 배우고 내일을 개발하다

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

[문제]

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

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

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

[입력]

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

[출력]

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

[알고리즘 분류]

• 자료 구조
• 우선순위 큐

[해설]

이 문제는 11279번 문제인 최대 힙과 반대되는 출력을 요구하는 문제이다. 따라서 최대 힙에서 사용했던 우선순위 큐의 특성을 이용하면 이 문제 또한 쉽게 해결할 수 있다.
먼저, 우선순위 큐 (priority_queue)는 최댓값이 top에 오는 성질을 가지고 있다. 그러므로, 입력되는 수들에 -를 붙여 push 하도록 하면, "음수 절대값이 작을수록 크다"는 성질로 인해 다음과 같은 순서로 큐에 들어가게 된다. ( 9, 7, 4, 1 --> -1, -4, -7, -9 )

이렇게 하고 top을 출력하게되면 -1, -4, -7, -9의 순서로 나올 것이다. 하지만, 이는 문제가 원하는 답이 아니므로 다시 -를 붙여 이를 원래 값으로 출력하게 되면 정확히 문제가 요구하는 답을 구할 수 있다.

[정답 코드]

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

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

[결과]