17503 백준 파이썬

맥주파뤼~~

heap은 알콜이 낮은 순서로,. answer에는 prefer가 낮은대로 각각 두개의 heap을 사용했다.

입력된 값을 바로 heap에 넣어서 알콜도수가 낮은순대로 저장하고, 이들의 수가 n에 도달했을때, 만족도를 넘기지 못하면 answer의 값 중 가장 만족도가 낮은 것을 뺀다.

 

이때 만약 알콜이 가장 높은 것이면 두번째로 알콜값이 높은 값을 가장 높은 값으로 바꿔준다.

이걸 heap이 존재할때까지 반복하고, 없으면 -1를 출력하게 했다.

 

문제가 있었던 점은 second_alchol을 사용하지 않고, answer에서 반복문을 찾아서 maxalchol을 찾으려고 했더니 시간초과가 났다는 점이다.

 

시간초과가 난 코드

import heapq
n,m,k=map(int,input().split())
heap=[]
answer=[]
for _ in range(k):
    prefer,alchol=list(map(int,input().split()))
    heapq.heappush(heap,[alchol,prefer])
s=0
maxalchol=0
# heap에는 알콜이 낮은 순으로 들어감
while heap:
    alchol, prefer=heapq.heappop(heap)
    maxalchol=max(maxalchol,alchol)
    s+=prefer
    heapq.heappush(answer,[prefer,alchol])
    if len(answer)==n:
        if s>=m:
            print(maxalchol)
            exit()
        else:
            x=heapq.heappop(answer)
            s-=x[0]
            maxalchol=0
            for x in answer:
                maxalchol=max(maxalchol,x[1])
print(-1)

 

 

맞춘 코드

import sys
import heapq
input=sys.stdin.readline
n,m,k=map(int,input().split())
heap=[]
answer=[]
for _ in range(k):
    prefer,alchol=list(map(int,input().split()))
    heapq.heappush(heap,[alchol,prefer])
s=0
maxalchol=0
second_alchol=0
# heap에는 알콜이 낮은 순으로 들어감
# answer에는 perfer가 낮은 순으로 들어감
while heap:
    alchol, prefer=heapq.heappop(heap)
    if maxalchol<alchol:
        secondalchol=maxalchol
        maxalchol=alchol
    s+=prefer
    heapq.heappush(answer,[prefer,alchol])
    if len(answer)==n:
        if s>=m:
            print(maxalchol)
            exit()
        else:
            x=heapq.heappop(answer)
            s-=x[0]
            if x[1]==maxalchol:
                maxalchol=second_alchol
print(-1)