[프로그래머스] [JAVA] [Level 2] [스택/큐] 더 맵게

문제 설명

 

---

제한 사항

 

---

입출력 예

 

---

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;       

        // 오름차순 정렬된 큐
        PriorityQueue<Integer> heap = new PriorityQueue();
        
        // 우선순위 큐에 배열의 값 넣어주기
        for(int num:scoville){
            heap.add(num);
        }
        
        // 최상단의 값이 K보다 작거나 같을동안만 
        while(heap.peek() <= K){
            
            // 원소가 K보다 작긴 하지만 한개이기 때문에 섞을 수 없는 상황
            if(heap.size()==1){
                answer = -1;
                return answer;
            }
            
            // 오름차순으로 정렬되어 있기 때문에 최상단이 가장 낮은 수이고
            // poll을 했기때문에 다음 poll값은 그 다음으로 가장 낮은 수이기 때문에
            int a = heap.poll();
            int b = heap.poll();
            
            heap.add(a+b*2);
            answer++;
        }
        
        return answer;
    }
}

---

PriorityQueue

• 우선순위 큐
• PriorityQueue<Integer> pq = new PriorityQueue<>();
• import java.util.PriorityQueue -> import
• 숫자가 작을수록 우선순위를 높게 매김 -> 값의 크기를 오름차순으로 정렬해서 큐에 넣어줌
• Collections.reverseOrder()를 이용해 내림차순을 우선순위로 큐에 넣어줄수 있음

---

Queue 자료 구조

• FIFO 구조 - > FIRST IN FIRST OUT , 먼저 들어간 것이 먼저 나옴
• import java.util.Queue, import java.util.LinkedList -> import
• Queue<Integer> queue = new Queue<>() -> int형 큐 선언
• que.isEmpty() -> 비어있는지 true ,false로 반환
• que.offer(), que.add() -> 값 추가 
• que.poll() -> 첫 번째 값을 반환하고 제거, 없다면 null
• que.remove() ->  첫 번째 값을 삭제
• que.clear() -> que 초기화 
• que.peek() -> Stack의 가장 최근 값 조회