[BOJ] 2075. N번째 큰 수 Python

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

 

1. 해결방법

음... 솔직히 heapq 알고리즘에 대해서 완벽히 이해와 시간복잡도 또는 메모리에 대해서 잘 알고 있지 않는 이상 과연 heapq 를 떠올릴 수 있을까??

이 문제는 뇌빼기 코딩으로 2차원 배열을 저장하고 2중 for문을 한번 더 돌아서 리스트에 저장한 다음, 정렬해서 찾으려고 한다면 시간복잡도는 어떻게든 되겠지만 메모리라는 벽에 부딪혀 버린다. 

가장 중요한 포인트는 heapq 라이브러리와 함께 한 줄씩 리스트로 입력받고, 리스트의 개수가 N개 넘어가지 않는 선에서 계속 조건을 다는 것이다.

1. 우선순위 큐 안에 들어있는 원소의 개수가 N개 미만이라면   
=> 우선순위 큐에 집어넣는다.
2. 우선순위 큐 안에 들어있는 원소의 개수가 N개라면   
       1) 현재 확인하고 있는 숫자가 우선순위 큐의 최솟값보다 작은 경우        => 무시한다.   
       2) 그 외의 경우        => 우선순위 큐의 최솟값을 제거하고 현재 확인하고 있는 숫자를 우선순위 큐에 삽입한다.

 

 

2. 정답코드

import sys
import heapq

input = sys.stdin.readline

N = int(input())

heap = []
for _ in range(N):
    numbers = list(map(int, input().split()))
    for num in numbers:
        if len(heap) < N:
            heapq.heappush(heap, num)
        else:
            if heap[0] < num:
                heapq.heappop(heap)
                heapq.heappush(heap, num)

print(heap[0])