[백준] 2075번 > N번째 큰 수

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

---

풀이

모든 수를 다 힙에 push하면 메모리 초과가 발생한다. 파이썬의 heapq모듈이 최소 힙을 만들어 준다는 점을 이용해야한다.

최소 힙의 크기를 N으로 제한하면 힙에 있는 수 중에서 첫번째 원소가 바로 N번째 수가된다.

첫번째 줄의 N개의 수는 모두 push하여 힙에 넣어준다.

두번째 줄부터 N-1개의 줄은 현재 힙에 들어가있는 첫번째 원소와 비교하여 만약 입력값이 더 크다면 heappop을 하여 첫번째 원소를 삭제하고 새로운 값을 push해준다. 그렇지 않은 경우에는 아무것도 하지않으면 된다. 

import sys
import heapq
input = sys.stdin.readline
n = int(input())
queue = list(map(int, input().split()))
heapq.heapify(queue)
for _ in range(n-1):
    for i in list(map(int, input().split())):
        if i > queue[0]:
            heapq.heappop(queue)
            heapq.heappush(queue, i)
print(queue[0])