[프로그래머스] 디펜스 게임 / priority_queue

 

Level.2

 

문제

준호가 처음 가지고 있는 병사의 수 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 해주세요.

 

풀이

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq; // 낮은값부터 출력하는 우선순위큐
    int i = 0;
    for(i=0 ;i<enemy.size(); i++){
        if(k>0){
            pq.push(enemy[i]);
            k -= 1;
            continue;
        }
        
        if(pq.top() < enemy[i]){
            n -= pq.top();
            pq.pop();
            pq.push(enemy[i]);
        }
        else {
            n -= enemy[i];
        }
        
        if(n<0) return i;
        
    }
    
    return i;
}

 

해결방법

1. 처음부터 k번째까지 무적권을 쓴다고 생각하고 enemy 배열을 오름차순 정렬인 우선순위 큐에 k번째까지 push 한다. 
2. 우선순위큐의 맨 첫 번째 값이 현재 라운드의 enemy보다 작다면, 
   현재 라운드에 무적권을 썼다 치고, 병사의 수 n에서 우선순위큐 첫 번째 값을 빼주고 pop 한다.  
3. 이 과정을 거쳐서 n이 0보다 작아지거나 더 이상 공격해 오는 적군이 없다면, 현재 라운드수인 i를 리턴한다. 

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/142085#

프로그래머스