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

디펜스 게임 142085

🏕 문제 설명

---

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 
디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 
디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 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 해주세요.

🏐 풀이

---

먼저 48점 맞은 . . 코드는 다음과 같다.

#include <queue>
#include <vector>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    priority_queue<int> army;
    priority_queue<int, vector<int>, greater<int>> skill;
    
    if (k >= enemy.size()) return enemy.size();
    for (int i = 0; i < enemy.size(); i++) {
        if (skill.empty() || k > 0) {
            skill.push(enemy[i]);
            answer += 1;
            k -= 1;
        }
        else {
            int army_top, skill_top = skill.top();
            skill.pop();
            
            army.push(enemy[i]);
            army_top = army.top();
            army.pop();
            
            if (min(skill_top, army_top) > n) return answer;
            else {
                n -= army_top;
                
                if (skill_top < army_top) {
                    n -= skill_top;
                    n += army_top;
                    
                    skill.push(army_top);
                    army.push(skill_top);
                }
                else {
                    skill.push(skill_top);
                    army.push(army_top);
                }
                
                answer += 1;
            }
        }
    }
    return answer;
}

엄~~ 청 길고 비효율적 이여도, , 뭔가 내 생각대로 진행될 것 같아서 도대체 "왜안돼!!?" 를 고민했다.

접근법이 약 50%만 맞은게 아닐까 싶다 ㅎ ㅎ
왜 위와 같이 작성했는지는 다음과 같은 풀이를 하기 위해서였다.

skill, army 라는 priority_queue 를 만들고, skill 은 오름차순, army 는 내림차순으로 할당한다.

나는 skill 이라는 queue 에 무적권을 사용한 라운드를 표현하고 싶었다. 따라서 지나간 라운드들 중 제일 enemy[i] 의 크기가 큰 라운드만 추가하고 싶었다.

또한 army 의 경우 무적권을 사용하지 않은 라운드로, 사용하지 않은 라운드 중 가장 enemy[i] 의 크기가 작은 순으로 정렬하여 skill과 비교하고 싶었다.

이렇게 하면 위처럼 skill과 army의 top을 비교하여, army의 top이 더 큰 경우 서로의 라운드를 교체하고 싶었다.

이러한 로직으로 구현하고자 했으나, . . 48점 을 맞음 . .

그래서 다시 고민을 해보니 굳이 queue 를 두개나 쓸 필요도 없었고, 각 크기를 교환할 필요도 없었다.

어차피 k 개만 무적권을 사용하면 되기 때문에 각 라운드마다 k만큼만 queue 의 크기를 유지 시키면 되는 것 !
-> 왜냐하면 . . . 계속해서 해당 라운드를 비교해 나가기 때문에 유지만 무적권을 k번 썼다는게 제일 중요

따라서 k개 보다 queue 의 크기가 큰 경우 가장 작은 값(오름차순으로 하면 top이 제일 작다.) 을 n과 비교하여 n 보다 작다면 n에서 해당 값을 빼주고 pop 을 해준다. (어차피 지나간 라운드기 때문에 pop 해도 상관 없다)

💨 코드

---

#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;
    
    if (enemy.size() <= k) return enemy.size();
    for (int i = 0; i < enemy.size(); i++) {
        pq.push(enemy[i]);
        if (pq.size() > k) {
            if (pq.top() > n) return answer;
            n -= pq.top();
            pq.pop();
        }
        answer += 1;
    }    
    return answer;
}

🪀 어려웠던 점

• 어렵게 생각하지 말자 . . . . . . . .