프로그래머스 lv2 디펜스 게임 - Java 그리디

 

 

문제를 잘 읽어보자

N의 병사를 갖고 있고, 상대방의 병사가 배열이 주어진다.

상대방의 병사를 순서대로 만나고, 싸우면 내 병사는 N -= 상대 병사 수가 된다.

여기서 아이템이 있는데, "무적권" 이라는게 있다. 상대방 병사가 몇명이던 그냥 넘어가게 되는데.

이 무적권을 적당히 활용하면서 최대한 많은 라운드를 견뎌보자~

 

결국 정리하면

만나는 상대방들 중 가장 높은 병사들 수 에서 무적권을 사용해야한다. 

아우 욕심쟁이

바로 그리디가 생각났다.

 

일단 순차적으로 적들을 상대하므로, 무적권 수 만큼 큐에 담아준다.

이후로 상대방을 만날때 마다 큐에 들어간 병사 개수에서 가장 적은 병사수와 비교하면서 큐에 담아준다면

큐 내부에는 만나는 상대 병사들 중 가장 많은 병사들만 담기게 된다.

 

 

예를 들어 내 병사가 10명이고

3 5 2 1 7 2 4 순서로 상대를 상대한다고 치자,

무족권은 4개라면

바로 앞에 있는 네 무리의 상대병사를 큐에 담아준다. [3,5,2,1]

 

그럼 이제 [7,2,4] 와 비교해주면 된다.

큐의 내부에서 가장 작은 값이랑 다음 만나는 적과 비교를해서

큐의 값이 더 작다면 교체를 해준다.

교체 시 큐 내부에 있던 값은 (예시에선 1) 내 병사수에서 빼준다.

이를 반복하면 큐 내부에는 내가 만나는 상대 병사들 중 가장 높은 숫자들만 담기게 된다.

 

그렇다면 큐 내부 정렬이 필요한데 이때 우선순위 큐를 이용해 정렬된 상태에서 값을 비교해주었다.

 

import java.util.*;
 
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        
        for (int i = 0; i < enemy.length; i++) {
            // 무적권이 있으면 일단 큐에 넣기.
            if (k > 0) {
                pQ.offer(enemy[i]);
                k--;
            } 
            // 없다면 비교 시작.
            else {
                // 큐에 값이 있고, 큐에 맨 앞이 다음 만나는 적보다 약한경우.
                if (!pQ.isEmpty() && pQ.peek() < enemy[i]) {
                    n -= pQ.poll();
                    pQ.offer(enemy[i]);
                    // 큐에 있는 병력이 더 큰 경우 라이프에서 깜
                } else {
                    n -= enemy[i];
                }
            }
            // 라이프가 적으면 끝
            if (n < 0) {
                break;
            }
            answer++;
        }
 
        return answer;
    }
}