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

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

문제

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

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

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

 

아이디어

이 문제를 풀기 위해 우선순위 큐(Priority Queue)라는 개념을 사용해야 합니다.

우선순위 큐는 LIFO(Last In First Out)나 FIFO(First In First Out) 순서가 아니라 우선순위가 높은 데이터가 먼저 나가는 자료구조를 말합니다. 기본적으로 아무런 설정을 하지 않으면 숫자가 가장 큰 값이 우선순위가 가장 큽니다.

 

물론 우선순위를 새롭게 설정할 수 있습니다.

priority_queue<int, vector<int>, 비교함수> 이름;

다음과 같이 우선순위 큐를 선언하고 우선순위를 결정하는 기준에 대한 비교함수를 설정해주면 됩니다.

 

비교함수를 통해 자료구조 내 원소들의 swap 여부를 결정하는 것입니다.

이 같은 우선순위 큐의 특성을 이용해 자료구조 내에서 원소들을 오름차순으로 정렬하도록 하는 비교함수를 작성함으로써 위 문제를 풀 수 있습니다.

 

소스코드

#include <iostream>
#include<queue>
using namespace std;
int N;
struct cmp //swap여부 결정하는 비교함수
{
    bool operator()(int a, int b)
    {
        if(a>b) return true; //a가 b보다 크다면 swap
        else return false;
    }
};
priority_queue<int,vector<int>,cmp> pq; //priority_queue<int, vector<int>,비교함수> 이름;
int main()
{
    int N; scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        int x; scanf("%d",&x);
        if(x!=0) pq.push(x);
        else
        {
            if(pq.empty())printf("0\n");
            else
            {
                printf("%d\n",pq.top());
                pq.pop();
            }
        }
    }
    return 0;
}

 

- 최대 힙 : https://nomadsjh.tistory.com/42