[백준]_11279번 : 최대 힙(파이썬 and C언어)

11279번: 최대 힙

전략

파이썬에서는 그냥 리스트로 입력받고 최댓값을 max를 통해 도출하면 시간이 너무 많이 걸릴 것이기 때문에 파이썬에서 제공해주고 있는 heapq를 사용하자. heapq는 특정 리스트와 값을 주면 자동으로 정렬 기능을 수행해 준다. 그리고 heappop은 특정 리스트의 첫 번째 요소를 꺼내줌과 동시에 리스트에서 제거해 준다. 하지만 우리는 최댓값을 제거해야 하지 않는가? 따라서 값을 리스트에 집어넣을 때는 -1을 곱해준 상태로 집어넣는다. 이렇게 하면 절댓값이 가장 큰 원소가 가장 앞으로 나오게 되며 출력할 때는 -heap.heappop({리스트})를 해주면 된다.

---

시도 1(Python)

import sys
import heapq
input = sys.stdin.readline

heap=[]
for _ in range(int(input())):
    num=int(input())
    if num+len(heap)==0: print(0)
    elif num==0: print(-heapq.heappop(heap))
    else: heapq.heappush(heap,-num)

조건문에 리스트가 비어 있고 num이 0인 조건을 num+len(heap)==0 이라고 할 수 있는 이유는 num은 반드시 음이 아닌 정수이기 때문이다. 

시도 2(C언어)

#include <stdio.h>
#define MAX 1000001

int arr[MAX];
int size=0;
void insert_heap(int data){
    int idx=++size;
    while(idx!=1 && data>arr[idx/2]){
        arr[idx]=arr[idx/2];
        idx/=2;
    }
    arr[idx]=data;
}

int del_heap(){
    if(size==0) return 0;
    int ans=arr[1];
    arr[1]=arr[size--];
    int parent=1;
    int child=2;
    while(1){
        child=parent*2;
        if(child<size && arr[child]<arr[child+1])
            child++;
        if(child>size || arr[child]<arr[parent])
            break;
        int temp=arr[parent];
        arr[parent]=arr[child];
        arr[child]=temp;
        parent=child;
    }

    return ans;
}
int main(){
    int try;
    int user;
    scanf("%d",&try);
    for (int i = 0; i < try; ++i) {
        scanf("%d",&user);
        if(user==0) printf("%d\n", del_heap());
        else insert_heap(user);
    }
    return 0;
}