[백준] 2075. N번째 큰 수/Python - Silver3

❓문제

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

성능 요약

메모리: 115420 KB, 시간: 532 ms

분류

자료 구조, 정렬, 우선순위 큐

 

문제 설명

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=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

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

✍🏻풀이

우선순위 큐를 사용해 N번째 큰 수를 찾습니다.

최소 힙 큐를 이용하면 [12], [7, 12], [7, 12, 9], ... , [28, 31, 48, 35, 52], [31, 32, 48, 52, 35], [32, 35, 48, 52, 41], [35, 41, 48, 52, 49]로 저장됩니다.

위와 같은 방식으로 N번째 큰 수를 찾기 위해서 우선 힙에 N개의 수를 heappush를 이용해 넣습니다. 그리고 힙에 N개의 수가 있다면  heap[0]를 표의 수와 비교합니다. 표의 수가 현재 heap[0]보다 크다면 heap[0]를 제거하고 표의 수를 넣습니다. 이러한 방식으로 정렬을 하면 마지막에 heap[0]에는 N번째 큰 수가 위치하게 됩니다.

그러므로 heap[0]를 출력하여 N번째 큰 수를 나타내면 됩니다.

💻코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N  = int(input())
heap = []
for _ in range(N):
    for n in list(map(int, input().split())):
        if len(heap) < N:
            heappush(heap, n)

        if heap[0] < n:
            heappop(heap)
            heappush(heap, n)

print(heap[0])

📍후기

정렬이라고 해서 입력 다 받고 for문 써서 정렬한 다음에 힙 큐에 넣는 비효율적인 일을 벌였다... 그런데 굳이 그럴 필요 없이 힙 큐를 이용해 정렬해서 N번째 큰 수를 찾으면 되었다...