[백준] 1655 가운데를 말해요 (Python) - heapq

 

---

import sys
from heapq import heappush, heappop
n = int(sys.stdin.readline()) # input() 사용시 시간 초과 발생
smaller = []
larger = []
for i in range(n):
    now = int(sys.stdin.readline())
    if len(smaller) == len(larger): #가장 중요한 조건: left heap 과 right heap의 길이가 같거나 1차이여야 함
        heappush(smaller, -now) #smaller : max heap
    else:
        heappush(larger, now) # larger : min heap
    
    if smaller and larger and -smaller[0] > larger[0]: #길이를 먼저 맞춰 준 후, 값을 swap
        lp,sp = heappop(larger), heappop(smaller)
        heappush(smaller, -lp)
        heappush(larger, -sp)
    print(-smaller[0])

내가 이래서 백준 문제들을 정말 싫어한다.

고작 Input 하나로 시간초과 되고.... 테케도 별로 없어서 알수도 없고.. 어디서 틀려먹었는지 알수도 없고....

굉장히 나를 강하게 자라게 한달까 ㅋㅎㅋㅋ ㅋㅋㅋ ㅋㅋ 하 진짜

너무 불친절해서... 시간은 시간대로 잡아먹고, 조금만 더 고치면 풀 수 있을 것 같은데 ? 라는 느낌을 주면서

결국 못 풀어서 이유를 찾아보면.... input을 썼기 때문이라잖아 !!!!!!!!!! 진짜 너무 화가나

 

그래도 많이 알아간다.

1) 중간값을 빠르게 구할 땐 최대힙과 최소힙을 활용, 둘의 길이를 맞춰주는 조건을 이용하자
2) input() 보다 import sys, sys.stdin.readline()이 훨씬 빠르다. 
(몰랐던 거 내 잘못 맞고... 내가 멍청한 거 맞긴 한데 진짜 이거 하나때문에 하루를 썼다ㅜ)

 

 

백준 문제를 좀 더 풀어보자 ...

킹받고 빡돌아도 배울 점은 굉장히 많으니까..............