프로그래머스 디팬스 게임 - 자바

문제

풀이

import java.util.*;

public class Pro_디펜스게임 {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;

        int tmp = 0;
        Queue<Integer> q = new PriorityQueue<>((o1,o2) ->{
            return o2 - o1;
        });
        for(int i = 0; i < enemy.length; i++){
            tmp += enemy[i];
            q.add(enemy[i]);
            if(tmp > n){
                if(k > 0){
                    tmp -= q.poll();
                    k--;
                }else{
                    break;
                }
            }
            answer = i+1;
        }
        return answer;
    }
}

리뷰

몇 라운드까지 클리어할 수 있는지를 묻는 문제로
정렬을 사용하는 방식은 라운드가 꼬일 수 있어 불가능했다.

그렇다고 경우의 수를 일일이 따지는 것도 배열의 크기가 커서 불가능했다.
어느정도의 수가 큰값인지 그 비율이 얼마나 되는지 정하는 것도 너무 모호했다.

결론은 우선순위큐를 사용하는 것이다.

1. 일단 적의 수를 누적한다.
2. 적의 수가 내 병사 수 보다 커지면
   우선순위 큐에서 최대값을 뽑아 그 수를 적의 수에서 감소시킨다.
   (물론 반대로 내 병사 수를 차감하다가 병사수가 0보다 작아지면 우선순위 큐의 최대값만큼 병사를 복구하는 방식으로 해도 된다.)

이번 문제는 다른 사람의 아이디어를 참고해서 풀 수 있었던 문제였다.ㅜㅜ