[Python] 백준 알고리즘 2075번 : N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

👩‍💻문제 이해

힙 구조를 이용해 N x N 개의 숫자 중 N번 째 큰 수를 찾는 문제

숫자 자체를 찾는 것은 어렵지 않지만, 시간과 메모리를 고려하기 위해 힙 구조를 잘 활용해야 한다.

메모리 제한이 12mb이므로 입력값을 모두 저장해서 사용할 수 없다.

 

 

 

👩‍💻heapq 모듈을 사용해 절댓값 힙 구현 : 메모리 초과☠️

from heapq import heappop, heappush

n = int(input())
heap = []

for i in range(n):
    li = input().split()
    for j in li:
        heappush(heap, (-int(j), int(j)))
        
res = []
for i in range(n):
    res.append(heappop(heap)[1])
    # append를 사용하게 되면 heap이 아닌 list형태로 만들어지게 된다.
print(min(res))

 

 

 

👩‍💻heap전체를 검사하지 않고 N번째 큰 수 가 나오면 바로 출력  = heap의 크기를 N으로 유지 : 성공🌈

import heapq

n=int(input())
graph=[]
for i in range(n):
    graph.append(list(map(int, input().split())))

heap=[]
for i in range(n):
    for j in range(n):
        heapq.heappush(heap,graph[i][j])
        if len(heap) > n:
            heapq.heappop(heap)

print(heapq.heappop(heap))

 

 

👩‍💻heap전체를 검사하지 않고 N번째 큰 수 가 나오면 바로 출력(2)  =  heap의 크기를 N으로 유지 : 성공🌈

import heapq 
heap = []
n = int(input()) 

for i in range(n):
    li = map(int, input().split())
    for number in li:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
        else:
            if heap[0] < number:
                heapq.heappop(heap)
                heapq.heappush(heap, number)
print(heap[0])

 

 

 

 

✨Point✨

heap 구조에서 N번째 수를 구하는 방법
if len(heap) < n:
을 이용해 heap의 크기를 n으로 유지한다.