[정글 베이직 17] — 우선순위 큐 · 응급실 관리

📋 문제 소개

문제 설명

우선순위 큐를 사용하여 환자를 우선순위에 따라 처리한다. 숫자가 작을수록 우선순위가 높다 (1 > 2 > 3).

INPUT

(이름, 우선순위) 튜플 리스트 patients

OUTPUT

우선순위에 따라 처리된 환자 이름 리스트

예제

입력

patients = [("김철수",3),("이영희",1),("박민수",2)]

출력

처리: 이영희 (우선순위: 1) 처리: 박민수 (우선순위: 2) 처리: 김철수 (우선순위: 3)

💡 힌트

heapq 모듈 사용. heappush()로 힙에 추가, heappop()으로 최솟값 제거.

① 문제 이해

항목	내용
문제	환자를 우선순위(숫자 낮을수록 높음) 순으로 처리한다.
자료구조	최소 힙 (Min Heap) — heapq 모듈
예제	[("김철수",3),("이영희",1),("박민수",2)] → 이영희,박민수,김철수

② 핵심 아이디어

파이썬 heapq는 최소 힙을 지원한다. (우선순위, 이름) 튜플로 push하면 첫 번째 값 기준으로 자동 정렬된다.

import heapq
heap = []
heapq.heappush(heap, (1, "이영희"))  # (우선순위, 이름)
heapq.heappush(heap, (3, "김철수"))
heapq.heappush(heap, (2, "박민수"))

heapq.heappop(heap)  # → (1, "이영희") 먼저 나옴

③ 코드 분석

import heapq

def process_emergency_room(patients):
    heap = []

    for name, priority in patients:
        heapq.heappush(heap, (priority, name))  # ① 튜플로 push

    processed = []
    while heap:
        priority, name = heapq.heappop(heap)    # ② 가장 낮은 우선순위 먼저
        processed.append(name)
        print(f"처리: {{name}} (우선순위: {{priority}})")

    return processed

번호	코드	의미
①	(priority, name)	튜플 첫 번째 값 기준으로 힙 정렬 — 우선순위가 기준
②	heappop()	가장 작은 값(최고 우선순위)을 O(log n)에 꺼냄

④ 최대 힙이 필요하다면

# heapq는 최소 힙만 지원
# 최대 힙처럼 쓰려면 우선순위에 - 부호를 붙인다

heapq.heappush(heap, (-priority, name))  # 음수로 변환
priority, name = heapq.heappop(heap)
priority = -priority                      # 꺼낸 후 다시 양수로

💡 튜플 비교 규칙: 첫 번째 값이 같으면 두 번째 값을 비교한다. 우선순위가 같은 환자가 있을 때 이름 알파벳 순서가 영향을 준다. 실전에서는 (priority, index, name) 처럼 타이브레이커를 추가하기도 한다.

⑤ 시간복잡도

연산	시간	이유
heappush	O(log n)	힙 트리 높이만큼 버블업
heappop	O(log n)	루트 제거 후 힙 복원 (버블다운)

⑥ 핵심 정리

• heapq는 최소 힙. 숫자가 작을수록 먼저 꺼낸다.
• 튜플 (우선순위, 값) 로 push — 첫 번째 원소가 정렬 기준.
• 최대 힙 필요 시 -priority 로 부호 반전.
• push/pop 모두 O(log n).