프로그래머스 - 더 맵게 (자바)

Heap,PriorityQueue 연습

내가 보려고 씀

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이 출처 : https://easybrother0103.tistory.com/118

https://velog.io/@agugu95/Java-Heap-Binary-Heap

 

---

Priority Queue

• 우선순위 큐로 데이터 중에서 우선순위가 높은 데이터를 빠르게 알 수 있다.
• 큐와 연산이 동일하나 우선순위가 가장 높은 데이터를 알 수 있다.
  이를 통해 최대 힙과 최소 힙을 구현 가능하다.

● 최대 값이 우선순위인 큐 = 최대 힙
● 최소 값이 우선순위인 큐 = 최소 힙

• 우선순위 큐를 통해 데이터를 정렬하는 것이 heap sort

 

---

 

1. 우선순위 큐 사용
2. 모든 음식을 우선순위 큐에 넣은 다음, 큐가 빌 때까지 반복문을 돌리면서 음식을 하나씩 빼줌
3. 이때, 큐에서 뺀 음식의 스코빌 지수가 K보다 낮을 경우 큐에서 음식을 하나 더 빼 섞어주고 다시 큐에 넣음
4. 큐에 다시 넣는 것을 음식을 섞는 것으로 생각하여 카운팅
5. 모든 음식을 K 이상으로 만들 수 없는 경우
   • 큐에서 음식을 뺐을 때 해당 음식의 스코빌 지수가 K보다 낮고
   • 큐에 더 이상의 원소가 없으면 음식을 섞을 수 없을 때
   • -1 반환

※ ArrayList는 효율성 통과 못한다고 함.

import java.util.*;

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