[Programmers] 디펜스 게임

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

프로그래머스

0. Headers

 - 우선순위 큐 사용 및 Less 사용

#include <vector>
#include <queue>
#include <functional>
using namespace std;

 

1. 알고리즘

 - 우선순위 큐를 사용하여 적의 수를 저장

   - 이렇게 한다면 들어오는 값마다 최대값 갱신

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, less<int>> pq;
    // enemy [4, 2, 4, 5, 3, 3, 1]
    for (int i : enemy)
        pq.push(i);
    // enemy [ 4 ]
    // enemy [ 4, 2]
    // enemy [ 4, 4, 2]
    // enemy [ 5, 4, 4, 3]
}

 - 위 방식을 사용한다면 만약 플레이어의 병사와 적의 병사들을 빼면서 우선순위 큐에 저장하기 때문에 for문이 돌아갈 때마다 적의 최대 수를 갱신

 - 따라서 플레이어와 적의 병사가 싸우면서 플레이어의 병사 수가 음수로 떨어지고 무적권이 있으면 무적권 사용

    - 사용시 우선순위 큐에 있는 적의 수를 플레이어의  병사에게 더해주고 무적권 수 감소

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, less<int>> pq;
    int answer = 0;
    for (int i : enemy)
    {
        pq.push(i);        
        if (n - i < 0 && k > 0) // 플레이어 병사 - 적 병사 < 0 and 무적권 > 0
        {
            n += pq.top(); // 적의 가장 많은 병사 더함
            pq.pop();
            k--; // 무적권 감소
        }
        n = n - i
    }
}

 - 종료 조건

   - 플레이어의 병사 - 적 병사가 음수이고 무적권이 0개 일 경우 종료

   - 모든 적의 공격을 막았을 경우 적의 배열 수 리턴

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, less<int>> pq;
    int answer = 0;
    for (int i : enemy)
    {
        pq.push(i);      
        if (n - i < 0 && k > 0)
        {
            n += pq.top();
            pq.pop();
            k--;
        }
        else if (n - i < 0 && k == 0) return answer; // 병사 수 음수 및 무적권 개수 0
        n = n - i;
        answer++;
    }
    return enemy.size(); // 적의 배열 개수
}

 

2. 완성 코드

#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, less<int>> pq;
    int answer = 0;
    for (int i : enemy)
    {
        pq.push(i);      
        if (n - i < 0 && k > 0)
        {
            n += pq.top();
            pq.pop();
            k--;
        }
        else if (n - i < 0 && k == 0) return answer;
        n = n - i;
        answer++;
    }
    return enemy.size();  
}

Test Code