99클럽 코테 스터디 _ 18일차 TIL (우선순위 큐)

 

< 문제 >

[백준] 17503. 맥주 축제 / 실버1

---

< 풀이 >

코드 변수 정의

• N  :  선택해야 하는 맥주의 개수
• M  :  최소로 요구되는 선호도 합
• K  :  주어지는 전체 맥주의 개수
• beers  :  [선호도, 도수 레벨] 형태로 저장된 K개의 맥주 정보 리스트

 

• pq  :  선택한 맥주의 선호도를 저장할 최소 힙
• preference  :  현재까지 선택한 맥주의 선호도 합

---

Priority Queue
시간복잡도 : O(KlogN)

import heapq

def drink():
    N, M, K = map(int, input().split())
    beers = [list(map(int, input().split())) for _ in range(K)] # K개의 맥주 정보를 (선호도, 도수 레벨) 형태로 저장
    beers.sort(key=lambda x:(x[1], x[0])) # 도수 레벨을 기준으로 오름차순 정렬 (같다면 선호도 기준 정렬)

    pq = [] # 선택한 맥주의 선호도를 저장할 최소 힙 (우선순위 큐)
    preference = 0 # 현재까지 선택한 맥주의 선호도 합

    for beer in beers:
        preference += beer[0] # 선호도에 누적
        heapq.heappush(pq, beer[0]) # 최소 힙에 삽입

        # 선택한 맥주의 개수가 N개일 때
        if len(pq) == N:
            # 누적 선호도가 M 이상이면 현재 맥주의 도수 레벨을 반환
            if preference >= M:
                return beer[1]
            # M 미만이면 선호도가 가장 낮은 맥주 제거
            else:
                preference -= heapq.heappop(pq)
                
    # 조건을 만족하는 조합이 없는 경우 -1을 반환
    return -1

print(drink())

 

 

 

풀이 방식

1. 맥주 정렬
   • 도수 레벨이 낮은 것부터 탐색하면서 조건을 만족하는 최소 도수를 찾기 위해 정렬한다.
   • beers.sort(key=lambda x: (x[1], x[0]))
     • 도수 레벨(인덱스 1)이 작은 순서로 정렬
     • 도수 레벨이 같다면 선호도(인덱스 0)가 작은 순서로 정렬
2. 맥주 선택 (우선순위 큐 활용)
   • 현재 맥주의 선호도를 preference에 합산한다.
   • 맥주의 선호도를 최소 힙에 삽입한다.
   • pq의 크기가 N이면
     • preference가 M 이상이면 현재 맥주의 도수 레벨을 반환한다. (최소 도수 레벨 보장)
     • M 미만이면 선호도가 가장 작은 맥주를 heapq.heappop(pq)로 제거한다.
3. 결과 반환
   • 2번 과정에서 조건을 만족하는 도수 레벨을 찾으면 해당 도수를 반환한다.
   • 모든 맥주를 고려해도 M 이상의 선호도를 만들 수 없다면 -1을 반환한다.

---

< 회고 >

🤔 💭_

문제를 처음 접근할 때 combinations로 모든 조합을 구해서 조건을 만족하는 조합이 있는지 확인하면 풀 수 있다고 생각했지만 맥주 종류의 수가 최대 200,000인 것을 보고 바로 철회했다. 개수가 적은 경우에는 조합으로 쉽게 풀 수 있겠지만 이 경우에는 다른 방식을 사용해야 한다는 것을 느끼고, 알고리즘 분류에 우선순위 큐가 있음을 확인했다. 알고리즘 공부할 때 우선순위 큐를 공부하긴 했지만 문제에 적용해 본 경험은 없었던 것 같다. 그래서 이 문제를 우선순위 큐로 풀이할 생각을 하지 못했다.

 

---

우선순위 큐(Priority Queue)

우선순위 큐는 가장 중요한(우선순위가 높은) 요소가 먼저 처리되는 자료구조

→   일반적인 큐(Queue)는 선입선출(FIFO, First In First Out)

→   우선순위 큐는 우선순위가 높은 요소가 먼저 나오는 구조

 

 

🔹 특징

• 자동정렬
  • 요소를 삽입할 때마다 내부적으로 정렬하고 꺼낼 때 항상 최우선 요소가 반환된다.
• 힙(Heap) 자료구조 활용
  • 일반적으로 이진 힙(Binary Heap)을 사용하여 O(logN)의 시간복잡도로 삽입/삭제 가능
• 최소 힙(Min Heap) / 최대 힙(Max Heap)
  • 최소 힙(Min Heap, default)  :  값이 작은 요소가 먼저 반환된다.
  • 최대 힙(Max Heap)  :  값이 큰 요소가 먼저 반환된다.

 

🔹 Python heapq 모듈

 

Python에서 heapq 모듈을 사용하여 우선순위 큐를 구현할 수 있다.

 

최소 힙(Min Heap)

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
heapq.heappush(pq, 1)

# pq = [8, 5, 2, 1]
print(heapq.heappop(pq))  # 1
# pq = [8, 5, 2]
print(heapq.heappop(pq))  # 2
# pq = [8, 5]
print(heapq.heappop(pq))  # 5

 

 

최대 힙(Max Heap)

heapq는 최소 힙만 지원하기 때문에 최대 힙을 구현하려면 음수 변환을 활용해야 한다.

import heapq

pq = []
heapq.heappush(pq, -5)  # 음수로 변환
heapq.heappush(pq, -2)
heapq.heappush(pq, -8)
heapq.heappush(pq, -1)

# pq = [-1, -2, -5, -8]
print(-heapq.heappop(pq))  # 8
# pq = [-1, -2, -5]
print(-heapq.heappop(pq))  # 5
# pq = [-1, -2]
print(-heapq.heappop(pq))  # 2