[Baekjoon]백준 2075 N번째 큰 수(실버 3) - Python

문제설명

예제

문제를 살펴보면 N을 입력받아 N^2개의 수를 입력받고 N번째로 큰 수를 찾는 문제이다

사실 제일 간단한 방법은 우리 모두가 알고있다 모든 값을 배열에 입력받아 sort를 통해 정렬하고

이후 해당 index의 위치에 있는 값을 들고오면 된다

허나, 우리에게는 시간과 메모리는 한정적이기 때문에 해당 방법은 지양하는 것이 좋다

 

파이썬에는 heapq라는 모듈이 존재하는데, 이를 활용하면 문제를 어렵지않게 해결가능하다

우선, 첫번째 줄의 내용은 그대로 읽어와서 heappush()로 저장을 해준다

이후 두번째 줄부터는 다른 조건이 필요한데, 해당 리스트에는 heappush()로 인해 작은 값부터

순서대로 저장되어있을것이다 그렇다면 리스트에 저장된 가장 작은 값보다 입력받은 값이 더 크다면

해당 리스트를 갱신해야한다 즉, if문으로 값의 크기를 비교하는 부분이 하나 추가되어야한다

그리고 리스트의 크기를 유지해야하므로 heappop()을 통해 가장 작은 값을 없애주면 된다

 

해당 과정을 계속해서 반복하다보면 해당 리스트의 가장 첫번째 index(0)에는 N번째로 큰 값이 저장될 것이다

import sys, heapq
input = sys.stdin.readline

size = int(input())
graph = []
graph_row = list(map(int, input().split()))
for num in graph_row:
    heapq.heappush(graph, num)
    
#print(graph)
for _ in range(size-1):
    graph_row = list(map(int, input().split()))
    for num in graph_row:
        if graph[0] < num:
            heapq.heappush(graph, num)
            heapq.heappop(graph)
            
print(graph[0])