디펜스 게임

 public int solution(int n, int k, int[] enemy) {
        //  출력크기 조과라고 뜨는데!!

        int answer = 0;
        List<Integer> integerList = new ArrayList<>();

        // k수보다 작거나 같은 스테이지는 스테이지 수만큼 주기
        if (enemy.length <= k) {
            return enemy.length;
        }


        /// 최소한 k 수만큼 스테이지는 클리어 가능.
        for (int i = 0; i < k; i++) {
            integerList.add(enemy[i]);       // [4,2,4], k=3
        }
        answer = k;

        int tempK = k; // 순서
        int tempN = n;  // n의 토탈값..

        /// 하나씩 배열에 넣고 가장큰 k개의 숫자만 제거하고 그 합이 n보다 작다면 ok
        Loop:
        while (true) {
            integerList.add(enemy[tempK]);
            // 내림차순 정렬해서
            Collections.sort(integerList, Collections.reverseOrder());

            for (int i = k; i < integerList.size(); i++) {
                tempN = tempN - integerList.get(i);
                if (tempN < 0) {
                    break Loop;
                }
            }
            tempK++;
            answer = tempK;
            tempN = n;
        }


        return answer;
    }

추측 : 시간 초과가 발생하는 부분은 배열을 내림차순 정렬을 할때 ...

결국에는 라운드에서 가장 큰수들을 무적권으로 방어하고 작은수들로만 n명의 병사를 소모시켜야 된다...

이 과정에서 우선순위 큐(Priority Queue) , 이분탐색이라는 자료구조와 알고리즘 풀이방법을 알게 되었으며, 우선순위 큐는 이진트리 구조이다.

//PriorityQueue  타입으로 풀어보자! 우선순위에 따른 엘리먼트가 먼저 나가는 자료구조
    public int solution3(int n, int k, int[] enemy) {
        int answer = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        // 작은 수 부터 넣는 방식 { 2,4,1} -> [1 , 2, 4]순으로 들어간다.

        for(int i = 0; i<enemy.length; i++){
            queue.add(enemy[i]);

            // k까지는 round는 무조건 성공한다. k보다 라운드가 크다면 큰수부터 제거.
            if(queue.size()>k){
                Integer smallNum = queue.poll();
                n -= smallNum; // 가장 작은수를 뺀다.

                if(n<0){
                    break;
                }
            }

            answer++;
        }
        return answer;
    }