[프로그래머스] 디펜스 게임 c++

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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 해주세요.

입출력 예

n	k	enemy	result
7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

풀이

priority_queue<자료형, 구현체, 비교 연산자> 를 사용한 풀이이다.

구현체는 기본으로 vector<자료형>으로 정의됩니다.(priority_queue가 실제로는 vector 위에서 돌아간다는 뜻)

vector가 아니더라도 deque<자료형> , stl에서 힙을 구현하기에 충분한 자료구조면 다 됩니다. (random access iterator가 지원되어야 합니다) 근데 굳이 데큐 쓸 이유는 없다고 하니 기본값인 vector를 사용합니다.

 

1. 무적권을 enemy[i] 가 큰 값에 사용하기 위해 

우선 순위 queue를  사용하여 오름차순으로 값을 저장하도록 합니다.

2. queue에 저장된 요소가 무적권 k개를 초과하였다면 

 queue의 앞부분부터 꺼내, 적의 공격을 방어하기 위해 병사의 수를 소모시킵니다.

3. 다음 라운드 enemy[i+...] 보다 병사의 수가 적다면 해당 라운드를 반환합니다.

#include <string>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    if( k >= enemy.size()){
        return enemy.size();
    }
    int answer = 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){
            answer += pq.top();
            pq.pop();
        }
        if(answer > n){
           return i; 
            
         }
    }
    return enemy.size();
}

 

다른 풀이

#include <algorithm>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    priority_queue<int> q;
    for (int i = 0; i < enemy.size(); i++) {
        q.push(enemy[i]);
        n -= enemy[i];
        if (n < 0) {
            if (k == 0) {
                break;
            }
            n += q.top();
            q.pop();
            k--;
        }
        answer++;
    }
    return answer;
}