파이썬 알고리즘 220번 | [백준 1202번] 보석 도둑 -그리디 우선순위 큐

Yunny.Log ·2022년 7월 31일

Algorithm

목록 보기

225/318

220. 보석 도둑

1) 어떤 전략(알고리즘)으로 해결?

자료 구조
그리디 알고리즘
정렬
우선순위 큐

2) 코딩 설명

<내 풀이>


import sys
import heapq
n, k = map(int, sys.stdin.readline().rstrip().split())
jewerq=[]; bag = []

for nn in range(n) :
    m,v = (map(int,sys.stdin.readline().strip().split()))
    heapq.heappush(jewerq, (m,v))

for bb in range(k) : 
    bag.append(int(sys.stdin.readline().strip()))

bag.sort()

tmp =[]
res = 0
for i in range(k) : # 가방은 가장 작은 가방부터
    now_bag = bag[i]

    while jewerq and now_bag >= jewerq[0][0] : # 현재 가방 무게가 보석 무게보다 크면 
        now_jewe_kg, now_jewe_price = heapq.heappop(jewerq) # 가장 가치 큰 보석 peek 
        heapq.heappush(tmp, -now_jewe_price) # 가장 가격이 높은 보석 최대힙 만들기
    
    if tmp : 
        res-=heapq.heappop(tmp) # 마이너스로 저장해놔서 더하기 위해서 -

print(res)

<내 틀렸던 풀이, 문제점>

아예 쌩 시간초과


import sys
import heapq
n, k = map(int, sys.stdin.readline().rstrip().split())
jewer = []; bag = []

for nn in range(n) :
    m,v = (map(int,sys.stdin.readline().rstrip().split()))
    jewer.append((m,v))

for bb in range(k) : 
    bag.append(int(sys.stdin.readline().rstrip()))
bag.sort()
jewerq=[];bagq=[]

#내림차순 정렬 (가장 큰 가치/무게 -> ... )
for mm,vv in jewer :
    heapq.heappush(jewerq, (-vv,mm,vv))

#print(jewerq)

res = 0
for j in range(k) : #가방 갯수만큼 돌면서 
    tmp=[]
    for jj in jewerq :  
        just_for_sort, now_jewe_kg, now_jewe_price = jewerq[0] # 가장 가치 큰 보석 peek 
        if now_jewe_kg<bag[j] : 
            res+= now_jewe_price
            heapq.heappop(jewerq) # 보석 처치 했으니!~
            break
        else : 
            heapq.heappush(tmp,heapq.heappop(jewerq))
    jewerq+=tmp
    heapq.heapify(jewerq)

print(res)

7프로 시간초과

import sys
import heapq
n, k = map(int, sys.stdin.readline().rstrip().split())
jewer = []; bag = []

for nn in range(n) :
    m,v = (map(int,sys.stdin.readline().rstrip().split()))
    jewer.append((m,v))

for bb in range(k) : 
    bag.append(int(sys.stdin.readline().rstrip()))

bag.sort()

jewerq=[];bagq=[]

#내림차순 정렬 (가장 큰 가치/무게 -> ... )
for mm,vv in jewer :
    heapq.heappush(jewerq, (-vv,mm,vv))

#print(jewerq)

res = 0
while jewerq and bag:
        just_for_sort, now_jewe_kg, now_jewe_price = jewerq[0] 
        # 가장 가치 큰 보석 peek 
        j=0
        while True and j<len(bag):
            if now_jewe_kg<bag[j] : 
                res+= now_jewe_price
                heapq.heappop(jewerq) 
                # 보석 처치 했으니!~
                bag.pop(j)
                break
            j+=1
        
print(res)

이게 틀리네

import sys
import heapq
n, k = map(int, sys.stdin.readline().rstrip().split())
jewerq=[]; bag = []

for nn in range(n) :
    m,v = (map(int,sys.stdin.readline().strip().split()))
    heapq.heappush(jewerq, (m,v))

for bb in range(k) : 
    bag.append(int(sys.stdin.readline().strip()))

bag.sort()

tmp =[]
res = 0
for i in range(k) : # 가방은 가장 작은 가방부터
    now_bag = bag[i]
    while jewerq and now_bag > jewerq[0][0] : # 현재 가방 무게가 보석 무게보다 크면 
        now_jewe_kg, now_jewe_price = heapq.heappop(jewerq) # 가장 가치 큰 보석 peek 
        heapq.heappush(tmp, -now_jewe_price) # 가장 가격이 높은 보석 최대힙 만들기
    
    if tmp : 
        res-=heapq.heappop(tmp) # 마이너스로 저장해놔서 더하기 위해서 -

    elif not jewerq: 
        break #담을 수 없는 보석이 하나도 없다면 

print(res)

반례 :

2023.01.04 => 7프로 시간초과

import heapq
import sys

n,k = map(int,sys.stdin.readline().rstrip().split())
jew = []
tmp_jew = []
bag = []
answer = 0

for i in range(n) : 
    m,v = map(int,sys.stdin.readline().rstrip().split())
    jew.append((-v, m)) 
    # 보석 가치 ( 최소힙 구성 땜 마이너스 붙임 ) / 무게 

heapq.heapify(jew)
for i in range(k) : 
    bag.append(int(sys.stdin.readline().rstrip()))
bag.sort() # 가장 작은 가방에

for i in range(k) : 
    # print(bag, jew, tmp_jew)
    while jew : 
        jew_v, jew_m  = heapq.heappop(jew) # 가장 큰 보석을 밀어넣는다.
        jew_v*=-1
        if jew_m <= bag[i] : # 이 가방에 보석이 들어갈 수 있다면
            answer+=jew_v
            break
        else : # 가방에 보석이 못들어가는 무게면 다음 보석 검사 
            tmp_jew.append((-jew_v, jew_m))
    jew+=tmp_jew
    heapq.heapify(jew)

print(answer)

heappop 을 매번 하는게 아니라 조건에 부합할 때만 heappop 하는 것으로 하자


for i in range(k) : 
    while jew : 
    # 나는 while 에서 무조건 heappop 하게 함 -> 시간초과의 원인!!!!!!!??"
        jew_v, jew_m  = heapq.heappop(jew) # 가장 큰 보석을 밀어넣는다.
        jew_v*=-1
        if jew_m <= bag[i] : # 이 가방에 보석이 들어갈 수 있다면
            answer+=jew_v
            break
        else : # 가방에 보석이 못들어가는 무게면 다음 보석 검사 
            tmp_jew.append((-jew_v, jew_m))
    jew+=tmp_jew
    heapq.heapify(jew)