백준/ Silver 2 문제 , 백준 파이썬 2075 , N번째 큰 수

백준/ Silver 2 문제 , 백준 파이썬 2075 , N번째 큰 수

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
heap을 이용하여 입력을 받을때마다 정렬 후 마지막 첫번째 원소를 출력

 

<문제 출처>

 

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

2075번: N번째 큰 수

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

 

N x N 행렬 형태중에서 N 번째로 큰 숫자를 찾는 문제이다.

 

N개의 heap 을 가지고 1행 부터 N행까지 쭉 확인해가며 숫자들을 계속 초기화 시켜준다.

 

마지막 행의 원소를 지나면 N 개의 heap 만 남아있을텐데,

 

오름 차순으로 정렬되어있고, 그 heap의 0번째 인덱스가 전체에서 N번째로 큰 수 이다.

 

추가로, -1 번째 인덱스는 당연히 입력받은 숫자들에서 가장 큰 수 이다.

 

 

 

 

입력을 한번에 받아 저장한 뒤 처리하려면 메모리 초과가 발생한다.

 

그러니, 1행씩 입력을 받자마자 처리한다.

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

import heapq
import sys
input=sys.stdin.readline

N=int(input())
heap=[]
heapq.heapify(heap)

for _ in range(N):
    tmp=list(map(int,input().split()))
    for i in range(N):
        heapq.heappush(heap, tmp[i])
        if len(heap)>N:
            heapq.heappop(heap)
            
print(heap[0])