✍️Today I Learned

📅 2025-10-31

• 우선순위 큐
• 프로그래머스: 디펜스 게임

---

우선순위 큐(priority_queue)

우선순위 큐는 먼저 들어간 것이 먼저 나오는 일반 큐와 달리 우선순위가 높은 것이 먼저 나온다.
내부 구조는 Heap으로 이루어져 있다.

Heap

• 완전 이진 트리 형태 (마지막 레벨을 제외하고 모든 노드가 완전히 채워진다.)
• 부모 - 자식 간 특정 대소관계를 유지한다.
• 배열로 구현된다.

Heap의 핵심 규칙

• Max Heap
  부모 노드가 항상 자식보다 크거나 같음
• Min Heap
  부모 노드가 항상 자식보다 작거나 같음
• 부모 자식 간의 대소 관계는 보장하지만 형제간 순서는 보장하지 않는 부분 정렬

Heap을 사용하는 경우

• 계속 삽입/삭제 하면서 최솟값/최댓값만 필요한 경우
• 전체 순서는 필요 없을 때

프로그래머스: 디펜스 게임

문제 링크
문제 설명
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

풀이

라운드별 enemy의 수의 합계를 구하면서 그 중 상위 값 k개를 벡터에 넣고 반복문으로 항상 비교하는 것은 비효율적이라 Min Heap 우선순위 큐를 사용하여 문제를 풀었다.

#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    int totalRound = enemy.size();
    if(k>=totalRound) return totalRound;
    
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    int sum=0;
    int sumK=0;
    for(int i : enemy)
    {
        if(minHeap.size()<k)
        {
            minHeap.push(i);
            sumK += i;
        }
        else if(i>minHeap.top())
        {
            sumK -= minHeap.top();
            minHeap.pop();
            minHeap.push(i);
            sumK += i;
        }
        sum += i;
        if(sum-sumK>n)
        {
            break;
        }
        else
        {
            ++answer;
        }
    }
    
    return answer;
}

---

💡 느낀 점 (What I Felt)

---

출처 프로그래머스: 디펜스 게임