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

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/142085?language=cpp 

프로그래머스

이 문제는 준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어질 때, 준호가 몇 라운드까지 막을 수 있는지 구하는 문제이다.

 

문제를 해결하기 위해서 최소 큐를 사용하였다. 

최소큐에 각 라운드의 enemy 개수를 담아두고 만약 이 enemy를 담아둔 최소큐가 무적권 개수보다 많아진다면 sum에 가장 작은 enemy 개수부터 더해준다. 이때, sum이 병사의 수 n보다 커진다면 가지고 있는 병사 수로 적(enemy)을 막을 수 없다는 의미이므로 해당 라운드를 반환해 준다.

위 과정을 enemy 벡터의 끝까지 반복을 했을 때 라운드가 반환되지 않는다면 가지고 있는 병사 수로 적을 막을 수 있다는 의미이므로 enemy의 길이를 반환해 준다.

---

#include <string>
#include <vector>
#include <queue>
#include <functional>  // greater
using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int sum = 0;
    // 가장 작은 값부터 출력
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < enemy.size(); i++) {
        int e = enemy[i];
        pq.push(e);

        if (pq.size() > k) {
            // 가장 작은 값을 sum에 더해줌
            sum += pq.top();
            pq.pop();
        }

        if (sum > n) {
            // 해당 라운드 반환
            return i;
        }
    }

    return enemy.size();
}

참고: https://jaimemin.tistory.com/2210