프로그래머스[Java] - (Level2)더 맵게(Heap)

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

프로그래머스

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> pq = new PriorityQueue<Integer>();
        // 우선순위 큐에 배열값 저장
        for(int i : scoville)   pq.offer(i);
        
        // 우선순위 큐에 스코빌지수 K보다 값이 작을때 반복
        while(pq.peek() < K){
            // 현재 우선순위 큐에 값이 한개만 존재하고, 그값이 K보다 작으므로 스코빌지수를 만들 수 없음 -> -1 리턴
            if(pq.size() == 1)
                return -1;
            
            // 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
            int a = pq.poll();
            int b = pq.poll();
            pq.offer(a+(2*b));
            answer ++;
        }
        
        return answer;
    }
}

풀이

우선순위큐를 사용하는 문제로, 힙 자료구조에 대한 개념이 부족하고,, 우선순위큐는 사실 거의 처음 사용해 보는 것 같다. 다음에 시간날때 힙에대해 정리를 해야겠다.

 

우선순위 큐는 큐의 일종이지만, 큐와는 다르게 기존의 선입선출이 아닌 우선순위가 높은 순서대로 반환한다.

즉 위 우선순위 pq에 어떠한 값이 있든 우선순위가 가장 높은(가장 작은값) 값이 peek()에 의해 K와 비교가 된다.

K보다 작을때, 가장 작은 값 두 개를 빼내고 이 두 개의 값을 통해 새로운 값(스코빌지수)을 만든다.

 

즉 데이터들이 우선 순위에따라 자동으로 정렬되는 편리한 자료구조이다 !