2075 백준 파이썬

생각보다 까다로웠던 문제

import heapq
n=int(input())
m=[]
for _ in range(n):
    m.extend(list(map(int,input().split())))
reverse_sign = lambda x: x*-1
m=list(map(reverse_sign,m))
heapq.heapify(m)
for _ in range(n-1):
    heapq.heappop(m)
print(-heapq.heappop(m))

이렇게 모든 수를 힙에 집어넣고, 출력했더니 메모리 초과가 났다.

이유는 int가 32비트이기 때문이다. 32*1500*1500/1000000 = 72MB이기때문이다.

그래서 힙을 n개로 유지했다.

import heapq
n=int(input())
heap=[]
for _ in range(n):
    l=list(map(int,input().split()))
    for x in l:
        if len(heap)<n:
            heapq.heappush(heap,x)
        else:
            t=heapq.heappop(heap)
            if t<x:
                heapq.heappush(heap,x)
            else:
                heapq.heappush(heap,t)
print(heapq.heappop(heap))