프로그래머스 - 디펜스 게임 [C++]

이 문제는 우선순위 큐를 이용하여 푸는 문제이다. 이 문제를 처음 봤을 때, 그리디 아니면 DP 문제라고 생각했다. 그러나 DP 배열을 만들기에는 입력 값들이 너무 컸고, 그리디는 어떤 방식으로 동작하는 지 끝내 찾아내지 못했다.

 

그래서 검색을 통해 찾아본 결과 우선순위 큐를 사용하는 아주 간단한 풀이가 있었다. 우선순위 큐를 최소 힙으로 만들고, enemy에 대해 루프를 돌면서 최소 힙에 삽입한다.

이 때 최소 힙의 크기가 k보다 커지는 순간은 무적권의 사용 한도를 넘었다는 것이 되므로, 최소 힙에서 하나를 빼어 현재 가지고 있는 병사에 수에서 뺀다. 만약 이 순간에 남은 병사보다 최소 힙에서 추출한 값이 더 크다면 라운드를 더 이상 진행할 수 없는 것이므로 현재 인덱스를 리턴한다.

만약 루프가 모두 돌았다면 이는 모든 적들을 물리친 것이므로 enemy의 크기를 반환하면 된다.

 

알고리즘 문제를 풀다보면 어느새 그리디, dp, 이분 탐색 등 알고리즘적인 풀이만을 떠올리게 된다. 그래서 이 문제에 우선순위 큐를 쓴다는 생각 자체를 못한 것 같다. 문제를 마주할 때 자료구조 또한 풀이가 될 수 있음을 반드시 명심해야겠다.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    
    priority_queue<int, vector<int>, greater<int>> minPQ;
    
    if (enemy.size() <= k) {
        return enemy.size();
    }
    
    int soldier = n;
    for (int round = 0; round < enemy.size(); round++) {
        minPQ.push(enemy[round]);
        
        if (minPQ.size() > k) {
            int temp = minPQ.top();
            minPQ.pop();
            
            if (temp > soldier) {
                return round;
            }
            
            soldier -= temp;
        }
    }
    
    return enemy.size();
}