프로그래머스 / 디펜스 게임 / C++

처음엔 구조체로 입력에 들어있는 가장 큰 값들을 k의 갯수만큼 인덱스와 함께 넣고, 값들을 0으로 바꾸어서

1라운드부터 진행하는 식으로 했는데 이렇게 하면 큰 오류가 있습니다.

 

k=4라고 가정할때, 3 3 3 3 5 5 5 5 가 입력이면 n이 12가 넘으면 위의 풀이가 정답이 될수 있지만 그게 아니라면

k를 다 뒤에서 써버리는 로직이기 때문에 올바른 답을 도출 할 수가 없습니다.

 

결국 이 풀이는 틀린 풀이었고 일단 n을 사용해가면서 0보다 작아질때, 지나왔던 곳에서 가장 큰 숫자가 있었던

라운드를 지우는 방법의 풀이가 정답을 받을 수 있었습니다. 이 풀이에서 놓칠 수 있는 부분은 k를 다 사용하기

전에 인덱스가 enemy의 크기를 넘어서는 경우가 있을 수 있어서 마지막에 return enemy.size();가 꼭 들어가야 합니다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int solution(int n, int k, vector<int> enemy) {
    priority_queue<int> pq;
    
    if (enemy.size() <= k)
        return enemy.size();
    
    int idx = 0;
    
    while(idx < enemy.size())
    {
        pq.push(enemy[idx]);
        n -= enemy[idx];           
        if (n < 0)
        {
            if (k==0)
                return idx;    
            k--;
            n += pq.top();
            pq.pop();              // 4 3 2,2,2,9
        }
        idx++;
    }
    
    return enemy.size();
}