[C++ 백준 풀이] 1927번 : 최소 힙 / 11279번 : 최대 힙 (Priority Queue 활용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver 상위에 해당하는 문제들인 1927번 : 최소 힙, 11279번 : 최대 힙 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

또한 자료구조 힙(Heap) 구현 문제를 C++의 Priority Queue를 활용하여 풀고 이에 대해 해설을 정리할 것입니다.

최소 힙 문제와 최대 힙 문제는 정렬 순서만 다르고 같은 문제이므로, 이 포스트에서 함께 다루도록 하겠습니다.

 

 

1927번 : 최소 힙

 

먼저 최소 힙 문제입니다.

힙을 이용해서 풀라고 하였으나 훨씬 간단하게 풀이하는 방법을 알려드리고자 우선 순위 큐를 활용해보겠습니다.

우선 문제를 보면 10만 이하의 명령 개수 N에 대해 노드 key 값들이 입력되면, 가장 작은 값들이 제거되기 쉽도록 준비해두었다가 0이 입력될 때마다 최솟값만 뽑아서 출력하고 해당 노드를 제거하는 문제입니다.

 

 

↓ 복사가 가능한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

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

int main() {
    int N, input;
    priority_queue<int, vector<int>, greater<int>> pq;
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
        scanf("%d", &input);
        if(input == 0) {
            if(!pq.empty()) {
                printf("%d\n", pq.top());
                pq.pop();
            }
            else printf("0\n");
        }
        else pq.push(input);
    }
}

 

우선 priority queue를 선언하였는데, 일반적으로 우선순위 큐는 순위가 높은 것을 가장 앞에 두고 있기 때문에 기본 형태는 내림차순 배열입니다.

그렇기 때문에 최솟값을 가장 빨리 배출하는 형태인 오름차순으로 정렬을 하기 위해서는 우선 순위 큐에 greater<int>로 compare 기준을 설정해주어야 합니다.

선언 이후에는 N을 입력받고, N개의 명령을 처리하는데 0인 경우는 최솟값을 pop 해주어야 하므로 empty가 아니라는 조건 하에서 top에 있는 값을 출력 먼저 수행 후 pop 해줍니다.

만약 0이 아니라면 그것은 key가 입력된 것이므로 우선순위 큐에 단순히 push만 해주면 됩니다.

 

 

 

 

 

이 문제는 코드를 올바르게 작성했음에도 시간 초과가 발생할 수 있는데, 왜 그런지는 모르겠지만 저의 경우 버퍼를 비우지 않아서 무한루프가 발생한 것 같습니다. (저의 개발환경에서는 잘 돌아가긴 했습니다.)

그래서 cstdio로 헤더 파일을 바꾸고 printf와 scanf를 사용했더니 제대로 채점이 되었습니다.

이 점 참고하시기 바랍니다.

 

 

11279번 : 최대 힙

 

다음은 위의 문제의 세트 문제인 최대 힙 문제입니다.

문제를 자세히 보면 알겠지만 정렬 조건만 빼고 문제의 모든 조건이 같음을 알 수 있습니다.

따라서 이번에도 우선 순위 큐를 사용하되, 정렬 순서만 내림차순으로 바꾸면 됨을 유추할 수 있습니다.

 

 

↓ 사용 가능한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

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

int main() {
    int N, input;
    priority_queue<int> pq;
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
        scanf("%d", &input);
        if(input == 0) {
            if(!pq.empty()) {
                printf("%d\n", pq.top());
                pq.pop();
            }
            else printf("0\n");
        }
        else pq.push(input);
    }
}

 

바로 풀이해보면 코드는 위의 문제와 거의 대부분이 같고, 우선순위 큐를 선언하는 부분에서 조건이 빠짐을 알 수 있습니다.

그 이유는 위에서도 이야기했듯 priority queue는 우선 순위가 높은 것을 우선으로 정렬하므로 기본 정렬 조건이 내림차순이기 때문입니다.

따라서 위와 같이 작성 후 제출하면 바로 정답 처리를 받으실 수 있습니다.

 

 

제출해보면 같은 시간인 24ms에 처리가 완료되고 정답 처리가 됨을 확인할 수 있습니다.