stack vs. heapq 문제 차이 비교

🔥 핵심 한 줄 요약

heapq는 “여러 후보 중 최선 1개를 계속 고르는 문제”
stack은 “앞에서 한 선택을 뒤에서 취소해야 하는 문제”

이 한 줄을 기준으로 보면 대부분 문제가 정리된다.

---

1️⃣ heapq 문제

• 회의실 배정
• 동시에 열리는 회의의 최대 개수
• 또는 필요한 최소 회의실 수

---

📌 이 문제에서 우리가 반복하는 질문

“지금 시작하는 회의가 기존 회의 중 가장 빨리 끝나는 회의를 재사용할 수 있는가?”

👉 매 순간 여러 회의 중 ‘가장 빨리 끝나는 회의 1개’만 중요

---

📌 그래서 heapq가 딱 맞음

• q에는 현재 진행 중인 회의들의 종료 시간
• q[0] = 가장 빨리 끝나는 회의
• 그 하나만 보면 됨 ❗

for start, end in info: 
    if q and q[0] <= start: # 재활용 가능 
        heapq.heappop(q) 
    heapq.heappush(q, end)

 

📌 과거 선택을 취소하지 않음

• 이미 시작한 회의는 되돌리지 않음
• 단지 “끝났는지”만 확인

---

2️⃣ 반대로 stack 문제는 뭐가 다를까?

❌ 크게 만들기(백준 2812) 에서 우리가 묻는 질문

“현재까지 선택한 숫자 중 어떤 걸 버릴지 다시 결정해야 하는가?”

정답: YES

---

📌 예제 다시 보기

 

4177252841 K=4

진행 중:

4
41
417 ← 7이 1보다 크고, 4보다 크니까 차례대로 빼주기
77
772 ← 2 등장 → 앞의 7은 유지
7725 ← 5 등장 → 앞의 2는 제거해야 더 큼 ❗
7752

 

👉 이미 선택한 숫자를 다시 취소해야 함

---

❌ heapq로는 이게 불가능

heapq는:

• “가장 큰 것”을 알려줄 뿐
• 누가 언제 들어왔는지
• 앞자리에 있는지
• 지금 지워야 하는지

👉 이 정보들을 전부 잃어버림

---

3️⃣ 구조적으로 비교해보자

기준	heapq (회의실)	stack (크게 만들기)
후보 개수	여러 개	사실상 연속된 과거 선택
관심 대상	항상 “최선 1개”	바로 직전 선택
과거 선택 취소	❌	✅
순서 유지	중요 ❌	필수 ✅
핵심 연산	최솟값 조회	pop / push
문제 본질	자원 관리	선택 수정

---

4️⃣ 결정적인 질문 3가지

✅ 질문 1

지금 선택이 나중에 취소될 수 있는가?

• YES → stack
• NO → heapq 가능

---

✅ 질문 2

후보가 여러 개 있고, 그중 최선 하나만 중요할까?

• YES → heapq
• NO → stack

---

✅ 질문 3

입력 순서를 반드시 유지해야 하나?

• YES → stack
• NO → heapq 가능

---

5️⃣ 두 문제를 한 문장으로 비교하면

회의실 문제

“지금까지 열린 회의 중 가장 빨리 끝나는 것 하나만 알면 된다”

크게 만들기

“앞자리에 있는 작은 숫자는 언제든지 취소될 수 있다”