[99클럽 5기] 코딩테스트 스터디 18일차 TIL - 우선순위 큐

[Silver I] 맥주 축제 - 17503 

[문제 링크](https://www.acmicpc.net/problem/17503)

🗝️오늘의 학습 키워드 (Keyword)

• 우선순위 큐
• 정렬
• 그리디

---

💻본인의 언어로 내용 정리 (Today I Learned)

맥주는 [선호도, 도수]로 표현이 된다. N일동안 N병의 맥주를 마셔야 할 때, 선호도가 M 이상이 되도록 하는 도수의 최솟값을 구해보자.

 

문제에서 함정이 여러 개 있었는데, 무조건 N병을 마셔야 한다는 것이고, 선호도가 M 이상이어야 한다는 것이다.

즉, 한 잔을 통해 호감도 M을 만족해도, N병까지 맥주를 마셔야 한다.

 

이 점에 유의하며 알고리즘을 설계해보자.

 

💡알고리즘 풀이

N, M, K = map(int, input().split())

# 맥주 종류 순으로 (선호도, 도수)
beers = []
for _ in range(K):
    v, c = map(int, input().split())
    beers.append((v, c))

beers.sort(key = lambda x : x[1]) # 도수 기준으로 정렬

입력받은 맥주에 대한 인자 값을 하나의 리스트에 담아준다. sort()를 통해 도수 기준으로 정렬한다.

 

list.sort(key = lambda x : x[1]) -> x = list, x[1] 에 대해서 정렬 시도

 

flavor = 0 # 맥주를 마신 후 선호도
heap = [] # 마신 맥주 저장

for beer in beers:
    if (len(heap) < N):
        heapq.heappush(heap, beer) # 맥주를 마시고
        flavor += beer[0] # 선호도 증가

        if (len(heap) == N): # N잔 마셨을 때
            if (flavor >= M): # 선호도가 M 이상이면
                print(beer[1]) # 그 때의 도수가 최솟값
                break
            else:
                flavor -= heapq.heappop(heap)[0] # 가장 처음 마신 맥주 제거

else: # 전체 조건에 맞지 않을 경우
    print(-1)

도수 순으로 정렬된 맥주를 차례대로 마신다.

 

힙에 마신 맥주를 저장하며, 맥주를 마실 때 마다 선호도의 합을 계산하고 이 값을 통해 목표 선호도와 비교를 진행한다. 조건에 맞지 않을 경우 힙에서 후순위로 미룬다. 이후 다음 맥주를 마시고, 선호도 검사 반복이다.

 

모든 조건을 만족하지 못하고 반복문을 빠져나왔을 경우, -1을 출력한다.

 

🗒️제출 코드

# 17503 맥주 축제

import heapq
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

# 맥주 종류 순으로 (선호도, 도수)
beers = []
for _ in range(K):
    v, c = map(int, input().split())
    beers.append((v, c))

beers.sort(key = lambda x : x[1]) # 도수 기준으로 정렬

flavor = 0 # 맥주를 마신 후 선호도
heap = [] # 마신 맥주 저장

for beer in beers:
    if (len(heap) < N):
        heapq.heappush(heap, beer) # 맥주를 마시고
        flavor += beer[0] # 선호도 증가

        if (len(heap) == N): # N잔 마셨을 때
            if (flavor >= M): # 선호도가 M 이상이면
                print(beer[1]) # 그 때의 도수가 최솟값
                break
            else:
                flavor -= heapq.heappop(heap)[0] # 가장 처음 마신 맥주 제거

else: # 전체 조건에 맞지 않을 경우
    print(-1)

---

💭오늘의 회고

꽤나 복잡했던 문제였다.

정렬과 우선순위 힙을 통해 자료 구조를 정리하고, 그리디 알고리즘을 통해 전체를 탐색하는 그러한 문제였다.

 

알고리즘이 여러 개 섞일 수록 난이도가 올라가는 느낌을 받는다. 경우 마다 어떠한 알고리즘을 선택할지, 선택한 알고리즘의 순서를 어떻게 배치할 것인지에 대한 고뇌가 참 힘든 것 같다.

 

해결방법은 끊임없는 반복 밖에 없는 것 같기에 오늘도 열심히 공부하는 하루가 될 수 있도록.

---

⬇️전체 소스코드⬇️

hanghae99/python_middler/18일차 맥주 축제/맥주 축제.py at main · Do-heewan/hanghae99