프로그래머스 - 디펜스 게임

1. 문제

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

프로그래머스

 

2. 접근 방식

우선순위 큐를 이용해 풀어야한다.

 

3. 구현

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        // 라운드 수가 무적권 수 이하이면 탐색할 필요가 없기에 바로 종료
        if (enemy.length <= k) {
            return enemy.length;
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i=0; i<enemy.length; i++) {
            pq.add(enemy[i]);
            
            if (pq.size() > k) {
                n -= pq.poll();
            }
            // 라운드를 다 못 끝낸 경우
            if (n < 0) {
                return i;
            }
        }
        // 라운드를 다 끝낸 경우
        return enemy.length;
    }
}

 

4. 정리

문제를 처음 접근하며 정렬이 필요하다고 생각을 했는데 그렇게 되면 현재 라운드에 대한 파악이 안되는 문제가 생긴다. 그래서 우선순위 큐를 이용해 풀어야 한다. 단순 자료구조 활용에 대한 문제를 너무 깊게 파서 오히려 헤맸던 문제였다.