[Algorithm] Programmers_디펜스 게임 in Java

💡 Programmers Lv2. 디펜스 게임:

가능한 라운드까지 가장 큰 적을 무적권으로 막으며 최대 라운드 진행

🌱 코드 in Java

알고리즘: Priority Queue

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        int len = enemy.length;
        PriorityQueue<Integer> e_max = new PriorityQueue<>((x, y) -> y - x); // Collections.reverseOrder()와 같이 처리해도 된다.
        if (k >= len) // 무적권이 라운드보다 크거나 같을 경우 라운드 수 반환
            return len;
        int i;
        for (i = 0; i < len; i++) {
            if (k == 0 && n < enemy[i])
                break;
            e_max.add(enemy[i]); // 우선순위큐에 적이 큰 수로 추가
            if (n < enemy[i]) { // 디펜스 할 수 없는 경우
                k--; // 무적권 사용하고
                n += e_max.poll(); // 해당 적만큼 우리편 추가
            }
            n -= enemy[i]; // 해당 적만큼 우리편 삭제(무적권 사용한 경우에도 동일 +,- 제로 만들기)
        }
        return i; // 인덱스와 라운드 수가 하나 차이나기 때문에 인덱스 반환해도 무방
    }
}

이번 문제는 어떤 라운드까지 진행하던 그 라운드 안에 가장 큰 적들을 무적권으로 없애고 얼마만큼의 라운드를 갈 수 있냐가 중요한 문제였기 때문에 우선순위큐가 바로 떠올랐다.
그 외에는 크게 어려운 것 없었음!

🧠 기억하자

1. PriorityQueue
   아래와 같이 선언할 수 있다.

• PriorityQueue<Integer> pq = new PriorityQueue<>()
• PriorityQueue<Integer> p1 = new PriorityQueue<>(Collections.reverseOrder());

한번 더 복습