[프로그래머스 / Java] 코딩테스트 연습: 디펜스 게임 (그리디)

난이도: Level 2

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

프로그래머스

 

입사 후 알고리즘을 푼지 너무 오래 되어서 오랜만에 한번 풀어보았다.

이 문제는 답을 보고 나서 어떻게 이런 기발한 생각을 다른 사람들은 할 수 있는건지 그저 감탄만 했다.

그리디는 제발 많이 안 나왔으면 좋겠다.

재능의 영역이란 것이 존재한다고 생각하는데, 그것이 코딩테스트에서는 그리디에 해당하는 것 같다.

자세한 설명과 주석은 시간될 때 추가하겠다.

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        if (k == enemy.length) {
            return k;
        }
        
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int e : enemy) {
            if (k > 0) {
                pq.add(e);
                k--;
            } else {
                int now = pq.poll();
            
                if (now < e) {
                    pq.add(e);
                    n -= now;
                } else {
                    pq.add(now);
                    n -= e;
                }

                if (n < 0) {
                    break;
                }
            }
            
            answer++;
        }
        
        return answer;
    }
}