[BOJ 2075번] N번째 큰 수

1. 문제

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

 

 

---

2. 문제 풀이

1) 첫번째 풀이

import heapq
import sys

N = int(sys.stdin.readline())
nlist = []
maxheap = []
    
for i in range(N):
    num = list(map(int, sys.stdin.readline().split()))
    nlist.append(num)
    

for numbers in nlist:
    for i in numbers:
        heapq.heappush(maxheap, (-i, i))
        
print(maxheap[N-1][1])

 

메모리 초과가 발생했다. 

 

생각을 해보니까 어차피 N번째 큰 수만 출력하는 거면 굳이 전체를 다 최대힙으로 입력 받지 않아도 되지 않나? 라는 생각이 들었다. 그래도 어떻게 해야 할지 감이 안잡혀서 서치 해보니까 힙의 크기를 N으로 유지하는 것이 중요한 문제였다. 

 

 

2) 두번째 풀이

힙이 비어있다면 해당 라인의 숫자를 넣어서 힙을 채우고, 그 뒤는 힙의 가장 첫번째 값(=가장 작은 값)보다 i값이 크면 해당 값을 바꾸는 식으로 힙의 크기를 N으로 유지하면서 채워 나간다. 

import heapq
import sys

N = int(sys.stdin.readline())
maxheap = []
    
for i in range(N):
    num = list(map(int, sys.stdin.readline().split()))
    
    if not maxheap:
        for i in num:
            heapq.heappush(maxheap, i)
    else:
        for i in num:
            if i > maxheap[0]:
                heapq.heappop(maxheap)
                heapq.heappush(maxheap, i)
        
print(maxheap[0])