(알고리즘 스터디) 8주차 수_Heap🌲_(Programmers) 더 맵게

🌟 프로그래머스 / Heap / Level 2 / 더 맵게

📃 문제

프로그래머스

🚫 제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

👀 입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

🤔 풀이 방법

➡️ Heap 을 우선 순위 큐를 통해 구현했다. 입력받은 배열을 큐에 넣은 후 위에서 부터 빼내면서 조건을 만족 시킬 때까지 반복하도록 한다.

💻 풀이 코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        // 우선 순위 큐를 활용한 minHeap 선언
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 원소 추가
        for (int i=0; i<scoville.length; i++) {
            minHeap.add(scoville[i]);
        }
        
        // 반복문 조건 (1) : 최소값을 가진 원소가 K 값보다 작다.
        // 반복문 조건 (2) : Heap 의 원소가 1개 밖에 없다.
        while (minHeap.peek() < K && minHeap.size() != 1) {
            int top = minHeap.poll();
            int next = minHeap.poll();
            
            minHeap.add(top + 2*next);
            answer++;
        }
        
        // 반복문을 다 돌았는데도 최소 노드 값이 K 보다 작다면 만들 수 없는 경우 의미
        if (minHeap.peek() < K) {
            return -1;
        }
        
        return answer;
    }
}
/*
기본 자료구조 : (우선순위 큐) 최소힙
*/

 

[level 2] Title: 더 맵게, Time: 1514.12 ms, Memory: 127 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@3c82282