2075번 N번째 큰 수

📌Problem

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번째 큰 수를 출력한다.

✍solution

(우선순위 큐)
1. heapq를 통해 문제 해결
2. n개를 기준으로 n개 이상일 경우 우선순위 큐의 첫번째 원소(제일 작은 수)와 다음에 들어올 수를 비교
3. 큐의 첫번째 원소가 새로 들어오는 수보다 작을때 첫원소를 빼주고 새로운 원소를 넣어주기

💻Code

import heapq
n = int(input())
hq = []
for _ in range(n):
    arr = map(int, input().split())
    for num in arr:
        if len(hq) < n:
            heapq.heappush(hq, num)
        else:
            if hq[0] < num:
                heapq.heappop(hq)
                heapq.heappush(hq, num)

print(heapq.heappop(hq))

💡Takeaway

• 메모리 양을 줄이기 위해 필요없는 원소를 제거하며 문제 해결