[C++] 디펜스 게임

[문제]

코딩테스트 연습 - 디펜스 게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

이분탐색을 이용해서 문제를 풀었다.

답 result를 이분탐색에서 탐색하는 값이라고 생각해보자.

이분탐색에서 함수를 이용해 우리들은 해당 요일(mid값)이 가능한지 아닌지를 파악해보고 만약, 해당 요일이 가능하다면 숫자를 올려서 start = mid + 1을 하면서 범위를 위로 올려주고 아니라면 end = mid - 1을 하면서 범위를 아래로 좁혀주자.

 

이분탐색에서 해당 날짜만큼 가능한지 아닌지 파악하는 isPossible 함수는 enemy를 처음부터 mid값만큼 복사해서 해당 날짜가 저장된 벡터를 정렬해준뒤 k번만큼 있는 무적권을 쓴 뒤부터 복사된 벡터의 내용들을 n에서 빼면서 해당 값이 가능한지 아닌지 파악하였다.

[회고]

이분탐색이 아니라 우선순위 큐를 이용해서 1부터 enemy 사이즈까지 가능한지 아닌지 파악하는 방식으로 간다면 더 빠를 것이다.

[코드]

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool isPossible(int n, int k, vector<int> enemy){
    bool answer = true;
    sort(enemy.begin(),enemy.end(),greater<int>());
    
    for(int i = k;i<enemy.size();i++){
        n -= enemy[i];
        if(n < 0){
            return false;
        }
    }    

    return answer;
}

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    
    //이분탐색 사용.
    //result만큼 가능한지 아닌지 파악해보자.
    
    int start = 0;
    int end = enemy.size();
    int mid = 0;
    
    while(start <= end){
        mid = (start + end) / 2;
        vector<int> temp;
        
        for(int i = 0;i<mid;i++){
            temp.push_back(enemy[i]);
        }
                
        if(isPossible(n, k, temp) == true){
            answer = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
    }    
    return answer;
}