[Python/파이썬] 백준 17503번 맥주 축제

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

코드

from heapq import heappop, heappush
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])  # 도수 레벨 오름차순 정렬


def solution():
    picked = []  # 고른 맥주들
    preference = 0  # 고른 맥주들의 선호도 합

    for b in beers:
        heappush(picked, b)
        preference += b[0]
        if len(picked) >= n:    # 맥주를 n개 골랐다면?
            if preference >= m:
                return b[1]  # 이번에 preference에 들어간 맥주
            else:
                preference -= heappop(picked)[0]

    return -1


print(solution())

 

자료구조

• beers : k개의 맥주 정보를 저장하는 배열이다. 각 요소는 [선호도, 도수 레벨]로 구성되어 있다.
• picked : k개의 맥주 정보 중 골라낸 n개의 맥주를 저장할 최소힙이다. 각 요소는 beers와 마찬가지로 [선호도, 도수 레벨]로 되어 있기에 선호도가 낮은 맥주가 먼저 `heappop()`된다.

코드 설명

1. k개의 맥주를 도수 레벨이 낮은 것부터 오름차순으로 정렬한다.
2. 1의 과정을 통해 정렬된 beers 배열의 맥주를 하나씩 골라서 최소힙인 picked에 `heappush`한다. 
3. 만약 picked의 길이가 n개가 되었다면 preference가 m 이상인지 확인한다.
   • m 이상이라면 picked에 포함된 맥주들 중  이번에 들어간 맥주의 도수 레벨이 가장 높을 것이므로 이번 맥주의 도수 레벨을 리턴한다.
   • m 이상이 아니라면 picked에서 heappop으로 가장 선호도가 낮은 맥주를 꺼내서 picked 배열에서 없애고 for문을 계속 돈다.
4. for문을 끝까지 돌며 모든 맥주에 대해 확인해도 n개의 맥주로 선호도 m 이상을 만들 수 없다면 -1을 리턴한다.

---

처음에는 이분탐색으로 범위를 좁혀보며 가능한 최소 레벨을 찾아보려고 했는데, 이렇게 하니 시간 초과가 발생했다. 아마 범위가 한 번 바뀔 때마다 beers에 대해 for문을 돌아야 하므로 그런 것 같다. 그래서 그리디와 우선순위큐를 사용하는 코드를 참고하여 수정했더니 됐다.

 

이 풀이는 우선순위큐의 사용방식이 매우 인상깊었던 코드였다. 코드 도수 레벨이 작은 것부터 정렬하여 하나씩 고르고, 고른 것이 n개가 넘었을 때는 고른 맥주들 중 선호도가 낮은 맥주부터 방출하는데, 선호도가 낮은 맥주부터 방출할 때 우선순위큐를 사용한다. 다양한 자료구조의 동작방식을 이해하고 적재적소에 활용하는 능력을 키워야겠다는 생각이 든 문제였다.