[백준] 2075 N번째 큰 수

📖 문제

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

💻 내 코드

import sys
import heapq
n=int(input())
heap=[]

for i in range(n):
    nums=list(map(int,sys.stdin.readline().split()))

    if not heap:
        for num in nums:
            heapq.heappush(heap, num)
    else:
        for num in nums:
            if heap[0]<num:
                heapq.heappush(heap, num)
                heapq.heappop(heap)
        

print(heap[0])

💡 풀이

• 다른 사람 코드 참고함
• 우선 순위 큐를 사용하는 방법이라고 함

    if not heap:
        for num in nums:
            heapq.heappush(heap, num)

• 힙이 비어있으면 입력된 숫자들로 heappush
• 이 때 힙에는 n개의 숫자가 들어가게 된다

        for num in nums:
            if heap[0]<num:
                heapq.heappush(heap, num)
                heapq.heappop(heap)

• 힙이 비어있지 않으면
  • 힙의 인덱스 0에는 최솟값이 저장되어 있으므로 그 최솟값보다 num이 크면 heappush를 하고 heappop을 해 최솟값을 삭제한다
  • 이렇게 하면 힙의 크기는 n개로 유지가 됨
• heappush를 모두 마치고 힙의 크기는 계속 n으로 유지되므로 마지막에 힙의 최솟값인 heap[0]을 출력해주면 n번째 큰 수를 찾을 수 있다