[프로그래머스/Level2] 디펜스 게임 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 우선순위 큐

- 적의 수를 순서대로 우선순위 큐에 저장한다. (무적권으로 방어할 라운드의 적의 수)

- 무적권의 수보다 방어할 라운드가 많은 경우, 적의 수가 가장 적은 라운드에서 전투해 병력을 감소한다.

- 병력이 0보다 적어지면, 게임이 종료되며 해당 라운드 수를 반환한다. / 게임을 클리어한 경우, 총 라운드 수를 반환한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length;  // 모든 라운드 클리어 가능할 경우 리턴 값
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 무적권 사용해 해치울 적의 수
        
        for(int i = 0 ; i < enemy.length ; i++) {
           pq.offer(enemy[i]); // 각 라운드의 적의 수 저장
           
            if(pq.size() > k) // 무적권 수보다 방어할 라운드가 많은 경우, 적의 수가 가장 적은 라운드 전투
                n -= pq.poll();
            
            if(n < 0) // 남은 병사가 없는 경우, 게임 종료
                return i;
        }
        
        return answer;  // 게임 클리어한 경우, 총 라운드 수 반환
    }
}

 

 

 

➕ 다른 풀이 방식

- 이분 탐색을 활용한 풀이

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

 

 

- 묘..하게 다른 풀이

[연습 문제] 디펜스 게임 - JAVA

import java.util.*;
 
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = enemy.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 거쳐온 최댓값 저장하기 위한 우선순위 큐
 
        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];    // 우선순위 큐에 적의 수를 저장
            pq.add(enemy[i]);
 
            if(n < 0) {    // 남은 병사 수가 0보다 적으면, 무적권 사용
                if(k > 0) {
                    n += pq.poll();    // 가장 큰 값에 대해 무적권 사용
                    k--;
                    continue;
                }
                answer = i;
                break;
            }
        }
        return answer;
    }
}

 

 

 

- 우선순위 큐를 내림차순 정렬해서 푸신 풀이

[프로그래머스] 디펜스 게임 JAVA

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

 

 

---

💦 어려웠던 점

- 데이터 크기가 너무 크길래 그리디, 정렬할 생각은 했는데, 우선순위 큐 (최대 힙) 사용할 생각은 못 했다.

- 무적권을 크기가 작은 데이터에 사용할 생각을 했었다. (하지만 무적권은 상대 enemy가 많은 라운드에 사용하는 것이었다,,)

 

 

🧐 새로 알게 된 내용

우선순위 큐(시간 복잡도 : O(logN))를 언제 사용하는지

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Java] 프로그래머스 [Level-2] 디펜스 게임

 

프로그래머스