[Coding Test][Python][백준] BOJ #2075 N번째 큰 수

#2075 N번째 큰 수

문제)

N×N의 표에 수 $N^2$개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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번째 큰 수를 출력한다.

---

풀이)

※ 풀이 아이디어

$N \le1500$ 이므로 $N^2$의 Matrix는 $1500 \times 1500 \times 4 bytes = 9MB$의 메모리를 차지한다. 하지만 추가적인 오버헤드를 고려해보았을 떄 메모리 제한 12MB를 초과할 가능성이 있다.
따라서 다른 자료구조를 사용하거나, row별로 처리하는 알고리즘을 생각해야한다.

우리는 N번째 큰 수 만을 유지하면 되지 때문에 이를 Priority Queue를 통해 유지하면 된다.

입력을 Matrix에 저장하지 말고 한 줄씩 입력 받으면서 Min - Heap의 최소값보다 입력값이 크다면 Heap에 넣어준다.
이로써 모든 입력을 받으면 Top - N 개의 값을 유지하게 된다.

 

import heapq

N = int(input())

pq = []
heapq.heapify(pq)

for i in range(N):
    row = list(map(int, input().split()))
    for j in range(N):
        if len(pq) < N:
            heapq.heappush(pq, row[j])
        elif len(pq) == N:
        	# 입력값 > Min heap의 최소값
            if row[j] > pq[0]:
                heapq.heappop(pq)
                heapq.heappush(pq, row[j])
print(pq[0])

---

※ 메모리 초과 코드

처음에 단순하게 접근하여 Matrix를 입력받아 1차원 List로 만든 후 정렬하여 답을 구하였습니다.

하지만 메모리 초과를 마주하고 다른 방법을 통해 해결하였습니다.

(백준에서 시간초과가 나는건 많이 봤지만 메모리 초과는 한번도 보지 못해서 당황했다..!)

N = int(input())

# 메모리 초과
# 결국 2차원 Array를 사용하면 메모리 초과
# => 다른 자료구조를 사용해야한다.
matrix = [list(map(int, input().split())) for _ in range(N)]

# 메모리 초과
matrix = []

for _ in range(N):
    matrix.extend(list(map(int, input().split())))

matrix.sort(reverse=True)

print(matrix[N-1])