더 맵게 (for JAVA)

이문제는 큐로 푸는 문제인데 난 그걸 눈치체지 못하고 그냥 풀었다. 힙 구조로 어떻게 개선해야 할지 모르기 때문이다

1차답안 (안되는데 개선하다 때려침) - 제발 테스트 케이스 좀..

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        if (scoville.length == 1 && scoville[0] < K) {
            return -1;
        } else if (scoville.length == 1 && scoville[0] >= K) {
            return 0;
        }
        Arrays.sort(scoville);
        int mix = scoville[0];
        for(int i = 1;i<scoville.length;i++) {
            if(scoville[i]<mix) {
                mix = scoville[i] + (mix * 2);
            } else {
                mix = mix + (scoville[i] * 2);
            }
            if (mix >= K) {
                return i+1; 
            }
        }
        return -1;
    }
}

하지만 정상적으로 배열로 풀었다 하더래도 효율성에서는 통과못하겠지 왜냐면 우선순위큐를 적용한 다른 답안들은 시간복잡도가 현격히 줄기 때문임 그러므로 이런방식으로는 통과는 불가능함..

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue();
        for(int i = 0;i<scoville.length;i++) {
           pq.offer(scoville[i]);
        }
        
        while(pq.peek() < K) {
            if(pq.size() == 1) {
            	return -1;            
            }
            int p1 = pq.poll();
            int p2 = pq.poll();
            int value = p1 + (p2*2);
            pq.offer(value);
            answer++;
        }
        return answer;
    }
}

우선순위 큐를 공부하고 적어본 내용들이다
우선순위큐 생성자의 경우 데이터를 넣을때 자동정렬이 되는 장점이 있기 때문에 많이 사용하는 방식이다 그래서 데이터를 넣을때도 그냥 넣으면 자동으로 정렬이 되어서 가장 적은 데이터 2개를 poll()로 추출할수가 있다