[백준][heap] 최소힙 python (200726)

1. 문제 설명 

 

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

1927번: 최소 힙

 

 

2. 풀이 

핵심 개념 : heap 을 다뤄야 함. 

0 이 아닌 다른 숫자가 들어왔을 때는 heappush

0 이 들어오면 heappop 한 뒤 print

     이때 pop 할 숫자 없으면 print 0

 

 

1) 내 풀이 (런타임 에러)

import heapq

N = int(input())
heap_list = []
heapq.heapify(heap_list)

for _ in range(N):
    num = int(input())
    if num != 0:
        heapq.heappush(heap_list, num)
    else:
        try:
            print(heapq.heappop(heap_list))
        except IndexError:
            print(0)

 

문제점 

1. 굳이 heapq.heapify(heap_list) 해줄 필요 없이 바로 heapq.heappush(heap_list, num) 해도 된다

2. input() 보다 sys.stdin.readline() 을 사용해야한다....!!!

 

 

2) 정답

import heapq
import sys

N = int(input())
heap_list = []
tt = []
for _ in range(N):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap_list, num)
        heapq.heappush(tt, num)
    else:
        try:
            print(heapq.heappop(heap_list))
        except IndexError:
            print(0)

 

 

+) 설명 

인풋 받는 메소드의 각각의 속도를 비교하자면

sys.stdin.readline  < raw_input() < input() 순서다. 

 raw_input() 은 문자열을 반환하고, input() 은 raw_input()을 evaluate 한 결과를 반환하기 때문에 더 걸림 

하지만 sys.stdin.readline 는 한줄의 문자열을 통째로 반환하는 형식.  

 

sys.stdin.readline : 한 라인 입력 받을 떄

sys.stdin : 여러 줄 입력 받을 때

 

 

3. 정리 

sys.stdin.readline 사용하는 습관을 들여봅시다.