백준 #2075 - [S2] N번째 큰 수 : 최소힙

(python3)

2075번: N번째 큰 수

 

메모리 초과, 최소힙, heapq

배열을 모두 받은 상태에서 맨 아랫줄 N개를 비교해서 가장 큰 값을 찾아서 pop 하는 방식으로 N번 수행해서 N번째 pop 되는 값을 구하려고 했는데, 메모리초과가 났습니다.

 

이 문제는 최소힙으로 정보를 읽어올때마다 항상 N개의 값만 저장하는 방식으로 해결할 수 있습니다.

파이썬에서는 배열을 최소힙 형태로 관리할 수 있는 heapq 모듈을 제공합니다.

아래 독스로 사용법을 확인할 수 있습니다.

heapq — Heap queue algorithm

최소힙에는 N개의 노드만 유지할거고, 새로운 정보를 넣고 N+1 개의 노드가 되면 헤드 (최소값) 을 pop 해줍니다.

모든 입력값에 대해 수행하고 나면, 헤드에 남은 값이 곧 우리가 찾는 N번째 큰 값이 됩니다.

 

코드

import sys
import heapq
def solution(input) :
    # 최소힙, 원소 N 개를 항상 유지
    # 모든 내용물을 다 넣었을때 head 가 우리가 구하고자하는 값이 됨

    H = []

    N = int(input().strip())
    
    cnt = 0
    for _ in range(N) :
        for n in list(map(int,input().split())) :
            heapq.heappush(H, n)
            cnt+=1
            if cnt > N :
                heapq.heappop(H)
    print(heapq.heappop(H))

        
input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac