[알고리즘] 프로그래머스 - 더 맵게(Heap)

1. 문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

2. 제한 사항

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

---

3. 풀이

• 우선순위 큐 이용

1. list에 scoville를 스코빌 지수가 작은 순서대로 넣음
   - 맨 앞에 가장 작은 스코빌 지수가 옴
2. list들의 원소가 모두 스코빌보다 커지거나, list 원소가 1개 남았는데도 K보다 작을 때 까지 반복
3. while문 안에서 list 앞의 두 원소를 꺼내 스코빌 공식에 대입해 다시 list에 삽입
   (우선순위큐이기 때문에 자동적으로 정렬됨)
   -> 한 루프마다 answer++ -> 횟수 증가

4. 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
		//모든 원소가 K이상인지 확인하기 용
		int check = 0;
		
		//새로 계산한 스코빌
		int ms=0;
		
		//가장 작은 스코빌
		int ls = 0;
		//두번쨰로 작은 스코빌
		int tls = 0;
		
		
		PriorityQueue<Integer> list = new PriorityQueue<>();
		
		
		for(int tmp : scoville) {
			list.add(tmp);
		}
		
		while(true) {
			check = 0;
			
			if(list.peek()>K) {
				break;
			}
			else if(list.size()==1 && list.peek()<K) {
				answer = -1;
				break;
			}

			
			ls = list.poll();
			tls = list.poll();
			ms = ls+ (2*tls);
			
			list.add(ms);
			answer++;
		}
		
		return answer;
    }
}