N번째 큰 수_2075

import heapq

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

len(heap)
for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
        else:
            if heap[0] < number: # (number가 minheap보다 클 경우) heap정렬을 유지한 채로 교체
                heapq.heappop(heap)
                heapq.heappush(heap, number)
                print(number, heap)
            #else : (number가  minheap보다 작을 경우) 아무 교체도 안일어남


print(heap[0])

sol2)

import heapq

n = int(input())

heap = []
for i in range(n):
    for j in list(map(int, input().split())):
        heapq.heappush(heap, j)  # j를 그대로 힙에 추가
        if len(heap) > n:  # 힙의 크기가 n을 초과하면 가장 작은 원소 제거
            heapq.heappop(heap)

print(heap[0])  # 힙의 가장 큰 원소가 결과

문제 접근법

원래는 문제 N^2개의 원소를 모두 입력받아 정렬 후 N의 해도 되는데 메모리 제한으로 인해 위와 같은 풀이를 제출 시 메모리 초과로 실패가 나게 됨

import heapq

n = int(input())

heap = []
for i in range(n):
    for j in list(map(int, input().split())):
        heapq.heappush(heap, -j)
        print(heap)

print((-1)* heap[n-1])

따라서 적당한 자료구조를 이용하면 되는데 우선순위 큐를 이용하면 이를 방지할 수 있다. 우선순위 큐는 일반적으로 힙을 이용해 구현하므로 힙 자료구조를 사용하였다.
정렬되어 있는 리스트의 [0]값 (가장 작은 값) 과 입력값을 비교하며 입력값을 힙에 넣으면 된다.
이때, 우선순위 큐 안에 들어있는 원소의 개수가 N개 미만이라면 우선순위 큐에 집어넣는다.
N개 이상이 될 경우 이때부터 힙정렬된 원소의 [0]값 과 새로운 원소(number)를 비교하여 새로운 원소가 클 경우 pop후 새로운 원소(number)를 넣는다. 작을 경우에는 무시한다.
이렇게 되면 N번째 큰 원소를 크기가 N인 Heap을 유지하면서 답을 찾을 수 있게 된다.

for _ in range(n):
    numbers = map(int, input().split())
    for number in numbers:
        if len(heap) < n: # heap의 크기를 n개로 유지
            heapq.heappush(heap, number)
            print(number, heap)
        else:
            if heap[0] < number: # (number가 minheap보다 클 경우) heap정렬을 유지한 채로 교체
                heapq.heappop(heap)
                heapq.heappush(heap, number)
                print(number, heap)
            #else : (number가  minheap보다 작을 경우) 아무 교체도 안일어남