2075. N번째 큰 수

2075 문제 보기

Difficulty : Silver 2

Status : Failed

Time : 00:17:24

접근 방식

메모리 초과가 계속 떠서 어떻게 메모리를 줄일지 계속 생각하다가 결국 정답을 본 문제..ㅜ
최소힙으로 구현하면 되는 문제였다.
단순히 최소힙으로 데이터를 넣어서 N번째로 큰 수를 구하면 또 메모리 초과가 된다!
그래서 항상 최소힙에서 관리하고 있는 데이터의 개수를 N개로 맞춰가면서 메모리 누수를 방지했다.

1. 최소힙에 데이터가 없는 경우

  if not hq:
    for num in num_list:
      heapq.heappush(hq, num) # 최소힙으로 데이터 채움

2. 최소힙에 데이터가 있는 경우
   • 최소힙의 가장 최솟값이 현재 순회 중인 리스트의 값보다 작은 경우, 기존 값 지우고, 순회 중인 리스트 값 추가

  else:
    for num in num_list: # hq에 값이 있는 경우 hq의 길이를 N으로 유지시키는 작업
      if hq[0] < num: # 최소값보다 순회 중인 리스트 내부 값이 큰 경우
        heapq.heappop(hq) # hq에서 hq의 최소값 pop
        heapq.heappush(hq, num) # 순회 중인 리스트 내부 값 push

최종 코드

import sys, heapq
input = sys.stdin.readline

N = int(input().rstrip())
hq = []

for i in range(N):
  num_list = list(map(int, input().rstrip().split()))
  if not hq:
    for num in num_list:
      heapq.heappush(hq, num) # 최소힙으로 데이터 채움
  else:
    for num in num_list: # hq에 값이 있는 경우 hq의 길이를 N으로 유지시키는 작업
      if hq[0] < num: # 최소값보다 순회 중인 리스트 내부 값이 큰 경우
        heapq.heappop(hq) # hq에서 hq의 최소값 pop
        heapq.heappush(hq, num) # 순회 중인 리스트 내부 값 push

print(hq[0])