📝 문제
N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.
이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.
🔒 제한사항
입력
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.
출력
첫째 줄에 N번째 큰 수를 출력한다.
📚 입출력 예제
입력 1
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
출력 1
35
🧐 아이디어
#1
흠,, 전체를 비교하며 찾으면 너무 비효율적이지 않을까??
최대 힙 이용해서 pop n번 하면 될 것 같은데 메모리 초과가 뜰까봐 걱정된다
-> 메모리 초과,,
#2
최대 힙을 사용해아한다는 생각에 매몰되어서 최소 힙을 사용할 생각을 못 했다!
입력받은 값을 heap에 저장하고 heap의 크기가 n을 넘어가면 heqppop을 한다.
그러면 작은 값들은 사라지고 최종적으로 heap에는 가장 큰 n개의 수만 남겨진다.
그중 가장 작은 값이 우리가 찾고 싶은 N번째 큰 수다.
🗝️ 풀이
import sys
import heapq
hq = []
n = int(sys.stdin.readline())
for _ in range(n):
for i in list(map(int, sys.stdin.readline().split())):
heapq.heappush(hq, i)
if len(hq) > n:
heapq.heappop(hq)
print(heapq.heappop(hq))
chick! chick!