문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/142085

구현방법

병사 n 명

무적 사용횟수 k 번

적이 나오는 배열 enemy[idx]

구현 문제 -> 최대힙을 이용한 구현 (우선순위 큐를 이용해서 가장 큰수에 음수를 붙여서 저장해둠. -> 이럴 경우 가장 큰 수가 작은수가 된다.

이분의 해설을 보고 이해가 확실하게 되었습니다. 생각보다 어려운 문제는 아니였습니다.

: https://school.programmers.co.kr/questions/43442

구현알고리즘

최대 힙을 이용한 구현

CODE

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;

        int Solders = n;


        PriorityQueue<Integer> enemyQueue = new PriorityQueue<>();
        //무적권보다 작거나 같으면 그냥 라운드 리턴하면됨.
        if (k >= enemy.length)
            return enemy.length;

        for (int index = 0; index < enemy.length; index++) {
            //병사수가 적 병사보다 크거나 같은경우 진행
            if (Solders >= enemy[index]) {
                Solders -= enemy[index];
                enemyQueue.offer(-enemy[index]);
                answer += 1;

                //병사수가 적을 때 무적권이 있는 경우
            } else if (k != 0) {
                k -= 1;
                if (!enemyQueue.isEmpty()) {
                    //이전 적의 병사가 더 많은 경우가 있을 때
                    if (-enemyQueue.peek() > enemy[index]) {
                        Solders = Solders + (Math.abs(enemyQueue.poll()) - enemy[index]);
                        enemyQueue.offer(-enemy[index]);
                        //이전 적의 병사가 더 적은 경우
                    }
                }
                answer += 1;
            } else {
                break;
            }
        }
        return answer;
    }
}