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

🍀 문제유형: 최소힙

🍀 문제설명 (링크 참조) 

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

 

🍀 풀이코드 

- 첫 시도는 최대 힙 만들어서 n번째 뽑아야지! 했는데 메모리 초과 ~.~

import heapq as hq
n = int(input())
h = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    for t in tmp:
        hq.heappush(h, -t)
print(-h[n-1])

 

- 그래서 뭐 어떻게 해야 되지.. 하다가, 최소힙을 각 행마다 만드는 것도 무리일 것 같고,, 고민하다가 해설집 힌트 조금 봤다. n번째로 큰 수는, 가장 큰 수 n개 중에 제일 작은 값이다의 다른 말.. 와우 아이디어,,

- 여튼 최소힙으로 문제 풀되, n개로 개수를 유지하면서, 최솟값을 반복적으로 제거하면 가장 큰수 n개만 남게 된다. 이때 n번째 큰 수는 곧 최소힙의 최솟값이니까 heappop()하면 된다. 

- 이때 주의해야 할 점은, else문에서 현재 값 push 후에 pop해야 한다. pop먼저 하고 push를 하게 되면, 최솟값을 제거하는 게 아닐 수도 있다. 

import heapq as hq
n = int(input())
h = []

for _ in range(n):
    tmp = list(map(int, input().split()))
    for c in tmp:
        if len(h) < n:
            hq.heappush(h, c)
        else: # 작은 숫자는 차례 차례 없애고 큰 숫자들로 채우는 거지 !!
            hq.heappush(h, c)
            hq.heappop(h)
            
print(h[0])

 

🍀 배운 점 

- "n번째 큰 수 = 가장 큰 수 n개 중 제일 작은 값" >> 이 아이디어는 최소힙이 오름차순으로 저장한다는 점에서 생각해낼 줄 알아야 한다는 점.. 연습만이 살길이겠지.