코딍코딍 2023. 6. 14. 18:45

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

소스코드

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < enemy.length; i++) {
            if (enemy[i] <= n) {
                answer += 1;
                n -= enemy[i];
                pq.add(enemy[i]);
            } else {
                if(k <= 0) break; //무적권이 없는 경우
                answer += 1;
                n -= enemy[i];
                pq.add(enemy[i]);
                n += pq.poll();
                k -= 1;
            }
        }

        return answer;
    }
}

 

 

해결방법

무적권을 적절한 시기에만 쓰면 되는 문제이다. 가진 병사의 수로 적을 디펜스 하다 병사의 수가 부족하면 무적권을 쓰면 된다. 이때 지금까지 디펜스 한 적들 중 가장 인원이 많았던 그룹에 무적권을 사용해야 한다. 그래야 적절한 시기에 사용하게 되고 최대한 많은 라운드를 갈 수 있다.

가장 인원이 많았던 그룹에 무적권을 사용하는 방법은 어렵지 않다. PriorityQueue(우선순위큐)를 사용해 쉽게 풀 수 있다.

디펜스할 때마다 적들의 수를 PriorityQueue에 저장하고 무적권을 써야 할 때 PriorityQueue에서 적들 중 가장 인원이 많았던 그룹을 뽑아서 무적권을 쓰면 된다.