프로그래머스 더 맵게(힙)

힙(Heap)

​

완전 이진트리의 일종이다.

반정렬 상태(완전히 정렬된 상태가 아님)이며 완전 이진트리와는 다르게 중복값이 허용된다.

삽입/갖제는 트리구조이기 때문에 OlogN 이므로 매우 빠르다

보통 우선순위 큐가 힙으로 많이 구변되는데, 배열과 리스트보다 효율적이기 때문이다.

​

힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다.

이를통해 여러 값 중에서 최소 값이나 최대값을 빨리 찾을 때 유용하게 이용할 수 있다.

​

힙 자료구조는 보통 배열을 이용하며, 0 번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다.

​

​

​

우선순위 큐

일반적으로 큐는 선입선출의 대기열 규칙을 가지고 있다. 말그대로 먼저온놈이 먼저 나간다.

​

priority Queue는 우선순위를 결정하여 들어온 순서와 상관없이 그 우선 순위가 높은 엘리먼트가 나가게 된다.

​

​

우선순위를 뽑으면 가장 낮은 스코빌의 음식이 나온다

그리고 한번더 실행하면 두번째 낮은 스코빌의 음식이나온다

첫번째+(두번째*2) < k 참이고

모든 수가 만족할때까지 반복한다.

​

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> que = new PriorityQueue<Integer>();
        
        
        for(int i = 0 ; i < scoville.length; i++) {
        	que.offer(scoville[i]); //que 에 값들을 삽입
        }
        
        int cnt = 0;
        while(true) {
        	// peek 을 하면  que 중 제일 작은 수가 나온다.( 제일작은 수가 나오는데 k이상이면 모든 수가  k 이상)
        	if(que.peek() < K) { // k 보다 작은경우   (2개가 들어와서 합쳐진다. 그럼 크기가 1)
        		int mix = que.poll()+(que.poll()*2);
        		que.offer(mix);
        		if(que.size() < 1 && que.peek() < K) {
        			cnt= -1;
        			break;
        		}
        		cnt++;
        		
        	}else {
        		break;
        	}
        	
        	
        }
        
        
        
        return cnt;
    }
}

현재는  자바에서 제공하는 유틸을 사용하였지만 

priorityqueue를 더 이해하기 위해  스스로  priorityqueue 를 구현해봐야겠다.