[파이썬][백준 2075][💛골드 5] (정렬, 우선순위큐)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

N번째 큰 수

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

🧞‍♂️ 내 풀이

이 문제는 숫자들을 전부 우선순위큐에 넣어서 N 번째로 큰것을 찾는 문제인데. 핵심은 “어떻게 우선순위큐에 넣을거냐” 인것 같다. 그냥 무식하게 전부 넣어서 N 번째까지 빼는 방법으로하면 이게 골드5가 아니겠지 라는 생각으로 풀었다.

내가 푼 방법은, N 개의 숫자만 계속해서 우선순위큐에 머물게하는 것이다. 그러면 마지막에 남아있는 N개의 숫자중 인덱스 0에 있는 숫자가 찾는 숫자일것이다.

즉, 크기가 N인 우선순위 큐에 NxN 만큼의 수를 넣어서 가장 큰 N개의 수만 남게 하는 것이다.

구현할때는 그럼 우선순위큐에 N 개를 채우고 나서부터는 하나 넣을때 마다 하나를 heapq.heappop() 해주면 된다. ***

🧞‍♂️ 파이썬 풀이

import sys, heapq
input = sys.stdin.readline

N = int(input())
h = []
for num in map(int, input().split()):
    heapq.heappush(h, num)
for _ in range(1, N):
    for num in map(int, input().split()):
        heapq.heappush(h, num)
        heapq.heappop(h)
print(h[0])

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기