알고리즘 풀이

입출력

• 입력
  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

문제 설명

n*n 2차원 배열에 한 줄에 위에 숫자가 무조건 아래 숫자보다 작을 때 n번째 큰 수를 찾는다.

1차

소팅해서 N번째 값을 출력한다 - 메모리 초과

N = int(input())
numbers = []
for _ in range(N):
    numbers+=list(map(int, input().split()))
numbers.sort(reverse=True)
print(numbers[N-1])

메모리 초과라는 것은 메모리가 너무 많이 쓰인다는 것이니 모든 2차원 배열을 갖고 있지 않고 필요한 특정 갯수만 가질 수 있는 방법? 우선순위큐 -> 힙큐를 사용해보자!

힙큐는 N개를 유지하면서 제일 작은 것은 out시킬 수 있다.

2차

list로 먼저 input을 다 받아서 힙에 돌리는 것도 메모리 초과다. 그때 그때 한줄씩 받아서 힙에 돌리는게 최선인 것 같다..

import heapq

N = int(input())
heap = []
heapq.heapify(heap)
for first_line_number in list(map(int, input().split())):
    heapq.heappush(heap, first_line_number)

for _ in range(1, N):
    for line_number in list(map(int, input().split())):
        heapq.heappush(heap, line_number) 
        heapq.heappop(heap)

print(heapq.heappop(heap))