[BOJ 2075] N번째 큰 수

Heap

BOJ 2075번 N번째 큰 수

문제

구조화

• 1차 접근
  • n번 째 큰 수이므로, max_heap으로 n번째 출력시도
  • 그러나 메모리 제한이 12MB이므로 메모리 초과 예상
• 2차 접근
  • 메모리 효율성을 위해 heap의 최대 크기를 n으로 설정
  • min heap 구성한 후 n크기 유지하며 첫번 째 값 출력
  • Process
    • 1행의 data는 그대로 min heap에 push
    • 2행부터
      • min value(root node 제거)
      • new data psuh
      • 반복
      • 이전 행보다 다음 행의 값이 더 크므로, 적어도 한 개 이상 제거 가능에서 출발한 관점
    • heap의 첫번 째 값 출력

예제 시각화

해답

import sys
import heapq as hq
input = sys.stdin.readline
n=int(input())
hqa = []
hq.heapify(hqa)
for i in range(n):
    data =list(map(int, input().split()))
    if len(hqa)==0:
        for num in data:
            hq.heappush(hqa,num)
    else:
        for num in data:
            hq.heappushpop(hqa,num)
print(hqa[0])