[프로그래머스] 디펜스 게임 자바 : 막히면 자료구조를 생각해봐

 

문제 : 디펜스 게임

프로그래머스

다음과 같이  n, k, 적들의 정보가 주어진 상황에서

->    7, 3, [4, 2, 4, 5, 3, 3, 1]

 

적의 최대값이 10^6 으로 들어올 수 가 있다.

 

알고리즘의 시간복잡도가 O(N^2) 은 시간 초과가 날 것을 알기때문에 

 

O(N*logN) 을 사용해야한다.

 

O(N*logN) 을 사용하여 해결 가능한 조건은 

 

1. 자료구조 : 힙

 

2.  알고리즘 : 탐색  , DP , 백트래킹  등

 

으로 갈릴것 같다  . 탐색의 순서는 인덱스 0 번을 기준으로 시작 하여 데이터의 크기가 매우큼으로  , 특정조건을 만족하면 break,return 를 이용하는 방식으로 설계를 들어간다. 

 

1.  k +1  의 수 만큼 heap 우선순위 큐 자료구조에 순차적으로 적의 정보를 저장한다 . 

2. heap 의 크기가 k 보다 크다면 heap 에서 pop 을 하여 나온 값을 현 n 값과 비교하고 , 값이 크다면 현 인덱스를 리턴, 아니면  n에서 차감후 진행한다.

 

 k 번째 까지 저장후 k+1 을 꼭 넣어야 힙 자료구조를 정확하게 활용이 가능하다.

 

최소 힙의 크기가 곧 k 의 크기 인것이 문제의 포인트 인것 같다.  (2 레벨인 이유)

 

import java.util.* ; 

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0 ;
        int total = enemy.length;

        if(total <= k) return total ;

        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i = 0 ; i < total ; i++) {
            q.add(enemy[i]);
            if(q.size() > k) {
                int item = q.poll();
                if(item > n ) {  
                    return i ;
                }
                n -= item;
            }
        }
        return total;
    }
}