[프로그래머스] 더 맵게 (Java, Heap, lv2)

 

---

문제 출처 

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

프로그래머스

 

문제 풀이

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수 가장 적은 두 가지 음식을 섞어 새로운 음식을 만든다 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

- K 이상 음식을 만들 수 있는 최소 턴 수 (만약 모두 섞었는데 못 구하는 경우 -1 리턴) 

- 우선 순위 큐, PriorityQueue 사용 (오름차순) , 시간 복잡도 O(NlogN) 이때 N은 스코빌 지수 배열 크기

- scoville 배열의 길이는 2 ~ 1,000,000

 

요약

while 루프를 돌면서 카운트를 증가 시킨다

- 큐의 크기가 2 미만인 경우 더 이상 음식을 만들 수 없으므로 -1을 반환한다

- 큐의 peek() 값이 K 이상이면 정상 종료한다

- 이외 주어진 공식에 따라 신규 음식을 큐에 추가하여 반복문을 수행한다 

 

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        Queue<Integer> que = new PriorityQueue<>(); // 오름차순
        for(int s : scoville) {
            que.add(s);
        }
        
        int answer = 0;
        while(true) {
            if(que.peek() >= K) break; // peek 값이 K이상이면 나머지도 K이상 만족
            if(que.size() < 2) return -1; // 음식이 하나면 더 이상 섞을 수 없다
            
            answer += 1;
            int v1 = que.poll();
            int v2 = que.poll();
            
            int next = v1 + (2 * v2);
            que.add(next);
        }
        
        return answer;
    }
}