백준 - N번째 큰 수 2075 (Python)

[Silver II] N번째 큰 수 - 2075
https://www.acmicpc.net/problem/2075

 

문제설명

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(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

 

출력

첫째 줄에 N번째 큰 수를 출력한다.

 

 

예제입력 / 예제출력

 

문제이해 및 코드설명

우선순위 큐를 풀기 위해 힙 자료구조를 사용하는 문제이다. 주어진 값들 중 N 번째로 큰 수를 구하는 문제이다.

우선 N개보다 입력값이 적을 때는 모든 값을 힙 자료구조에넣어준다. 이후 새로 들어오는 값이 기존에 있던 최소값 보다 작으면 가장 작은 값을 내보내고 새로운 값을 heap자료구조에 넣어주면된다. 이렇게 하면 최종적으로 힙 자료구조에는 제일 숫자가 큰 N개의 수들만이 남아있게 된다. N번째로 큰 수는 이들 중 제일 작은값이므로 heappop을 통해 값을 출력할 수 있다.

 

 

코드

import sys
import heapq

N = int(sys.stdin.readline())
heap = []

# 자료입력받기
for _ in range(N):
    nums = map(int,sys.stdin.readline().split())
    # 입력받은 자료 하나씩 확인, N개보다 적다면 무조건 heap에 넣어줌
    for num in nums:
        if len(heap) < N:
            heapq.heappush(heap,num)
        # N개보다 자료가 같거나 많은상황에서, 입력되는 값이 기존자료보다 크면 heap에 넣어줌
        # 최종 , heap에는 제일 숫자가 큰 N개만큼이 남음    
        else:
            if heap[0] < num:
                heapq.heappop(heap)
                heapq.heappush(heap,num)

print(heapq.heappop(heap))