[Java] 프로그래머스: 더맵게(Priority Queue 사용)

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

 

일반적인 큐(Queue)는 들어간 순서대로 나오는 FIFO(First In First Out)구조이다.  

       - 처음 들어간 값이 제일 먼저 나오는 형태

하지만 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나오는 구조이다. 

 

import java.util.PriorityQueue; 

// int형 
// 제일 작은 숫자를 우선순위로 둠(먼저 출력)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 제일 큰 숫자를 우선순위로 둠
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

// String형 
// 제일 작은 문자를 우선순위로 둠
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 
// 제일 큰 문자를 우선순위로 둠
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

// Queue 추가
priorityQueue.add(1);     
priorityQueue.add(2);     
priorityQueue.offer(3);   

// Queue 삭제
priorityQueue.remove();     // Queue의 첫번째 값 제거
priorityQueue.clear();      // 전부 제거

 

 

<문제>

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        // PriorityQueue 사용 (제일 작은 숫자를 우선순위로 지정)
        PriorityQueue<Integer> queue = new PriorityQueue();
        
        // 우선순위 큐에 음식의 스코빌 지수 추가
        for(int i = 0; i < scoville.length; i++){
            queue.add(scoville[i]);
        }
        
        // 가장 낮은 스코빌 지수가 K 이상일때까지 반복
        while(queue.peek() < K){
            // K 이상으로 만들 수 없는 경우
            if(queue.size() <= 1){
            	return -1;
            }
            int a = queue.poll();
            int b = queue.poll();
            
            // 두 음식 섞기
            int mix = a + b * 2;
            queue.add(mix);
            answer++;
        }
        return answer;
    }
}