백준 2075번: N번째 큰 수 [python]

난이도 : 실버 3
유형 : 우선순위 큐
https://www.acmicpc.net/problem/2075

문제 접근

N을 입력받고, N * N 2차원 행렬이 만들어지는데
이 때 N번째로 큰 수를 구하는 문제이다.

단 같은 열의 수들은 열이 클수록 숫자값도 큰 규칙을 띈다.

이걸 최소 힙으로 어떻게 구할까
-> 최소 힙(min-heap)을 사용해서 현재까지 가장 큰 수 N개만 유지하면 됨.
힙의 크기를 N으로 유지하면서 새로운 수를 넣을 때마다 최소값과 비교해, 더 크면 교체.

해답 및 풀이

import heapq
import sys
input = sys.stdin.readline


# 1. 입력
n = int(input())

heap = []

for i in range(n):
    row = list(map(int,input().split()))
    for num in row:
        if len(heap) < n:
            heapq.heappush(heap,num)
        else:
            if num > heap[0]:
                heapq.heappushpop(heap,num)

print(heap[0]) # n번째로 큰 수

어렵게 돌아가려다가 풀이를 보고 아차 한 문제.

2차원 배열을 만들어야 한다고 생각했지만 heap의 경우 heappop 을 통해 순서를 정렬하여 최솟값을 뽑아낼 수 있으므로 2차원배열을 만들지 않아도 되고 심지어 위칸이 바로 아래칸보다 작다는 조건도 쓰지 않아도 되었다.