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

문제링크

2075번: N번째 큰 수

 

문제이해

이 문제 도대체 무슨 소리를 하는거지?

문제를 이해를 하지 못했다. 나는 바보다.

문제예시를 보면 5 x 5 의 input이 들어오는데 이 수들 중에서 5번째로 큰 수를 출력하면된다.

52 - 49 - 48 - 41 - 35 순이므로 35를 출력하면 되는 것이다.

 

오답

처음에 모든 값을 최대힙에 넣어서 5번째 값을 출력하는 방식을 사용했는데, 메모리초과가 났다.

메모리 초과가 나올 것을 노리고 다른방법으로 풀기 원하는 문제였다.

import sys
import heapq
input = sys.stdin.readline

num = int(input())
heap = []
for i in range(num):
    arr = list(map(int,input().split()))
    for j in range(num):
        heapq.heappush(heap,-1*arr[j])

for i in range(num):
    if i == num-1 :
        print(-1*heapq.heappop(heap))
    else :
        heapq.heappop(heap)

 

문제풀이

주요로직은 최소힙을 사용하여 N개의 원소를 이미 넣어준 상태에서 시작하는 것이다.

그렇다면 최소힙이기때문에 최상위 값이 가장 작은 값이며 더 큰값이 들어올 경우에는 최상위 원소를 pop 시키고 다시 큰 값을 넣어줌으로써 N개를 유지시킨다. 그렇게 모든 값이 들어오게 되면 최소힙의 최상위 값이 N번째 수가 되는 것이다. 

import sys
import heapq
input = sys.stdin.readline

num = int(input())
heap = []
for i in range(num):
    arr = list(map(int,input().split()))
    if i == 0 :
        heap = arr[:]
        heapq.heapify(heap)
    else :
        for j in range(num):
            if heap[0] < arr[j] :           
                heapq.heappop(heap)
                heapq.heappush(heap,arr[j])

print(heap[0])