[백준/파이썬] 2075번

📍백준 2075번 문제

코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
h = []
for _ in range(n):
    temp = map(int, input().split())
    for i in temp:
        if len(h) < n:
            heapq.heappush(h, i)
        else:
            if h[0] < i:
                heapq.heappop(h)
                heapq.heappush(h, i)

print(h[0])

풀이

처음에는 메모리초과가 떴다 ... ㅎㅎ...
heap의 길이 < n을 힌트로 문제를 풀면 된다.
최소힙으로 풀었다.

• 힙의 길이가 n보다 작은 경우:
  그냥 heap에 추가하면 된다.

• 힙의 길이가 n보다 크거나 같은 경우:
  힙에서 가장 작은 값과 현재 값을 비교한뒤, 현재 값이 더 크다면 heap에서 첫번째 값을 빼고, 현재 값을 추가한다.

• 마지막 출력할 때, 최소힙이므로 n번째 가장 큰 값 = 힙 내에서 가장 작은 값이 된다. 첫번째 값을 출력하면 된다.