[프로그래머스, Java] Level2: 디펜스 게임

 

 

문제분석:

 

주어진 병사,  라운드마다 정해진 적들,  주어진 무적권

 

이 3가지의 정보를 사용하여 라운드를 최대 어디까지 도달할수 있는가를 구하는 문제다.

 

 

시작하기전에 , 제한사항을 보면   라운드는 100만 라운드며,  병사는 10억까지 다룰수 있다.

 

 

 

First Try:  이분탐색을 사용해보자.

 

아무리 큰 수라도  시간복잡도 log(n) 앞에선 엄청난 효율성을 보여준다. 

 

이분탐색의 기준은  당연히 우리가 구하고싶은 "최대 라운드" 이다. 

 

최소 라운드 = 1

최대 라운드 = 주어진 적 배치 배열의 길이

 

그 후, 중간값을 구한뒤   최소라운드 ~ 중간값 라운드 까지,

"내 군사들로 막을수 있는가?" 를 판별한다.  

 

막을 수 있다면 더 높은라운드 까지 막을수있는 가능성이 있으니, Up

 

막을 수 없다면  더 낮은 라운드를 탐색하기위해 Down 로직을 작성한다.

 

 

"내 군사들로 막을수 있는가?" 의 판별은

 

당연히, 최적의 상황에 무적권을 사용하고도  주어진 군사로 막을수 있는가다.

 

첫번째로, 배열을 잘라서 써야한다.  왜냐하면 정렬을 쓸 예정이기 때문이다. (전체 배열을 정렬하면 당연히 에러)

 

정렬을 한뒤,  제일 적의 숫자가 높은 라운드를 무적권을 사용할것이다.

 

참고로 자바에선 적들의 합을 double로 하셔야 테케 오류가 안납니다.

 

내 군사들이 적들을 막을수잇다면, True  없다면 False를 반환하면  문제풀이 끝!

 

전체 풀이:

 
import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        int min =1;
        int max =enemy.length; 
        
         while(min<=max){
            
            int mid=(max+min)/2;
            
            //충분히 막을수있으면 증가
            if(calculate(mid,k,n,enemy)){
                min=mid+1;
                answer=mid;
            }
            else{
                max=mid-1;
            }
             
        }
        
        return answer;
    }
    
    public boolean calculate(int mid, int k ,int n, int[] enemy){
        int[] arr= Arrays.copyOfRange(enemy,0,mid);
        Arrays.sort(arr);
        
        // int로 주면 범위가 넘어감.. 조심
        double sum=0;
        
        for(int i=0;i<mid-k;i++){     
            sum+=arr[i];
        }
        
        if(n>=sum){
            return true;
        }
           
        
        return false;
    }
}