예제 입력:
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예제 출력:
35메모리가 12MB로 넉넉하지 않아 최대한 리스트 사이즈를 작게 유지해야하면서도 시간제한이 1초라 정렬 알고리즘을 사용할 수 없었다.
어떻게 풀어야하나 찾아봤더니 파이썬 내장 자료구조 중에 heapq라는 것을 알게 되었다.
이런 구조로
왼쪽 이미지의 Min Heap은 리스트로 나타내면,
[10, 15, 30, 40, 50, 100, 40]이 된다.
(현재 인덱스 - 1) // 2 로 부모노드를 찾을 수 있다.
또한 메모리 크기를 만족하기 위해 heap의 크기를 입력 N으로 유지해주었다.
import sys, heapq
input = sys.stdin.readline
size = int(input())
matrix = []
for _ in range(size):
num_lst = list(map(int, input().split()))
if not matrix:
for num in num_lst:
heapq.heappush(matrix, num)
else:
for num in num_lst:
if matrix[0] < num:
heapq.heapreplace(matrix, num)
print(matrix[0])if not matrix 조건문을 통해 첫 12 7 9 15 5이 들어와서 heappush를 통해 이진트리가 생성되고 [5, 7, 9, 15, 12]
else 조건문을 통해 다음 줄의 입력들이 들어오며 0번째 인덱스 값보다 큰 값이 들어오면 heap의 이진트리에 들어오고 0번째 인덱스가 나가며 가장 작은 값이 다시 0번째 인덱스에 오게 되며 heap이 조절된다.
마지막 줄까지 다 정렬되고 나면 0번째 인덱스에 끝에서 N번째 큰 입력이 남아있게 된다.
