프로그래머스 - 디펜스 게임 (Java)

 

문제 개요

 

지문

 

제한사항

 

입출력 예

 

---

 

풀이

 

나는 이 문제를 풀 때 아래의 순서로 접근했다.

1. enemy 중 가장 많은 enemy가 등장할 때 무적권을 사용하자.
   • 반례로 가장 큰 값을 제거하더라도 현재 가진 병사의 수가 적어서 무적권을 사용해야 할 라운드까지 막아낼 수 없는 경우가 존재한다.
   • 예를 들어 n = 3, k = 1, enemy = {1, 2, 3}인 경우에 가장 큰 값인 3에서 무적권을 쓰고 싶어도 3에 도전하기 전에 모든 병사가 소모되는 경우가 존재하는 것이다.
2. 많은 enemy가 등장할 때 무적권을 사용해야 하므로, 현재 병사들로 막아낼 수 있는 최대를 구한 뒤, 우선적으로 그 안에서 enemy가 많은 순서대로 무적권을 사용하자.
   • 반례로 막아낼 수 있는 범위에서 무적권을 모두 소모했는데, 무작정 소모권을 사용했기 때문에 이후에 정작 무적권이 필요한 곳에서 사용할 수 없는 경우가 생긴다.
   • 예를 들어 n = 3, k = 1, enemy = {1, 3, 1, 1}인 경우에 무적권을 쓰지 않고 막아낼 수 있는 최대 라운드는 1라운드가 전부이므로 1라운드에서 무적권을 사용한다고 가정한다면, 최대 2라운드까지 막아낼 수 있다.. 그런데 만약 2라운드에서 무적권을 사용했다면 최대 4라운드까지 막아낼 수 있는 것이다.
3. 첫 라운드부터 순서대로 막다가 막지 못하는 라운드가 생긴 경우, 무적권을 사용한다. 그 뒤에 무적권을 모두 사용했다면 이전에 무적권을 사용했던 라운드 중 가장 enemy가 작았던 라운드말고 현재 라운드에서 무적권을 사용하면 막아낼 수 있다면 이전 라운드가 아닌 현재 라운드에서 무적권을 사용한 것으로 변경해 준다.

 

결론적으로 마지막 접근을 코드로 나타내는 과정은 조금 오래 걸렸으나, 통과는 되었다. 

 

위 접근 방식은 결국 우선순위 큐를 선언한 뒤에 해당 큐를 패스권이 사용된 라운드의 enemy를 저장하는 용도로 사용된 것이다.

 

그런데 위 방법 말고도 우선순위 큐를 패스권을 사용하지 않은 enemy를 저장하는 용도로도 사용할 수 있다. 해당 방식으로 작성한 코드는 아래에 첨부해 두겠다.

 

---

 

코드

 

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = k;
        if (k >= enemy.length) {
            return enemy.length;
        }

        Queue<Integer> queue = new PriorityQueue<>();
        for (int en : enemy) {
            if (queue.size() < k) {
                queue.add(en);
                continue;
            }

            if (en > queue.peek()) {
                queue.add(en);
                en = queue.poll();
            }

            n-= en;
            if (n < 0) {
                break;
            }

            answer++;
        }

        return answer;
}

 

코드 리뷰

1. 일단 위 코드는 정답이 나오는 걸 확인한 뒤에 조금 다듬은 코드이다.
2. 맨 처음에 answer=k로 둔 것은 무적권을 모두 사용할 것이기 때문이다. 
   • 그에 대한 반례는 무적권이 총라운드의 수보다 많다는 것인데, 만약 무적권이 더 많다면 문제 지문대로 enemy의 길이를 출력했다.
3. 우선순위 큐(PriorityQueue)를 사용했는데 그렇게 하지 않고 힙을 구현해도 상관은 없으나, 직접 구현까지 하진 않았다.
   • 그냥 new로 선언하면 가장 작은 수부터 꺼내어 쓸 수 있다.
   • 반대로 하려면 new PriorityQueue <>()의 매개변수에 Collections.reverseOrder()를 넣어주면 된다.
4. 반복문의 맨 처음에는 k의 수만큼 무적권을 사용하고 넘어가도록 처리했다.
5. k의 수만큼 무적권을 사용한 뒤에 오는 enemy부터는 이전에 무적권을 사용했던 라운드의 enemy와 비교하여 만약 이전에 무적권을 사용했을 때의 enemy가 현재보다 더 작다면 그때가 아닌 현재 라운드에서 무적권을 사용한 것처럼 처리하기 위해 queue.poll()을 사용했다.
6. en = queue.poll() 은 무적권을 사용한 라운드를 바꾸는 구문으로 우선순위 큐에 담긴 가장 작은 아이템을 꺼내어 적용하는 것이다.
7. n-en이 0보다 작다면, 현재로서 최선의 무적권 배치임에도 불구하고 더 이상 진행할 수 없다는 뜻이므로 break 하여 반복을 끝낸다.
8. 7번의 반대 상황이라면 막아낼 수 있는 최대 라운드를 의미하는 answer를 1 추가한다.

 

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i=0 ; i<enemy.length ; i++) {
            n -= enemy[i];
            queue.add(enemy[i]);

            if (n >= 0) {
                continue;
            }

            if (k <= 0) {
                return i;
            }

            n += queue.poll();
            k--;
        }
        return enemy.length;
}

 

---

 

제출 결과

 

제출 결과

 

위 두 방법 모두 제출해서 통과했다 ㅎㅎ