[프로그래머스] Lv.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) {
        int answer = 0;
        
        // min = 1, max = 5 mid = 3
        // 10만 * 
        int [] tmp = Arrays.copyOf(enemy, enemy.length);
        Arrays.sort(tmp);
        int min = tmp[0]; int max = tmp[enemy.length - 1];
        int mid = (min + max) / 2;
        for(int i = 0; i < enemy.length; i++) {
            //System.out.println("enemy: " + enemy[i]);
            if (k > 0 && enemy[i] >= mid) { // 적의 수가 mid값보다 같거나 클때
                k--;
            }
            
            else if (k == 0 || enemy[i] < mid) {
                if (n < enemy[i]) {
                    return i;
                }
                n -= enemy[i];
                //System.out.println("n: " + n);
            }
        }
        return enemy.length;
    }
}

 

이분 탐색을 사용하는 문제라고 생각하여 tmp 배열을 오름차순 후, min값과 max값을 찾아서 mid값을 구하고 배열을 순회하면서 적의 수가 Mid값 이상이라면 무적권을 사용하도록 구현하였다.

 

그리고 무적권의 횟수가 0이거나, 적의 수가 mid값 보다 작을 때는 정상적으로 계산을 하고, 만약에 현재 병사 수가 적의 수보다 작아지는 시점이 올 때 index를 리턴하도록 구현했다.

 

테스트 케이스는 통과했으나, 제출했을 때 틀렸다. 

 

우선순위 큐를 활용한 풀이

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < enemy.length; i++){
            n -= enemy[i];
            pq.add(enemy[i]);
            
            if (n < 0) {
                if (k > 0) {
                    int cur = pq.poll();
                    n += cur;
                    k--;
                }
                else {
                    break;
                }
            }
            answer++;
        }
        return answer;
    }
}

 

다른 방법이 생각나지 않아서 남의 풀이를 참고하니, 우선순위 큐를 사용하고 있었다. 우선순위 큐에 대해서 간략하게 알아보자면, 

 

자바 PriorityQueue 시간 복잡도

PriorityQueue시간 복잡도

요소 추가(삽입)	O(log n)
최우선 순위 제거	O(log n)
최고 우선순위 확인	O(1)
요소 검색	O(n)
크기(요소 수)	O(1)
배열/목록으로 변환	O(n)

 

높은 숫자가 우선순위를 가진다고 하면,

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

이런식으로 reverseOrder() 메서드를 사용하면 되고

 

낮은 숫자가 우선순위를 가진다고 하면

PriorityQueue<Integer> pq = new PriorityQueue<>();

이런식으로 구현하면 된다.

 

문제에서는 적의 수가 많을수록 우선 순위가 높게되고, 이 경우에 무적권을 사용해야 더 먼 라운드까지 진출할 수 있다. 그래서 높은 숫자에 우선순위를 부여하기 위해서 reverseOrder()를 사용해서 풀었다. 

 

 

 

 

 

출처: https://seasome1.com/%EC%9E%90%EB%B0%94-priorityqueue/#google_vignette