[Programmers] 더 맵게

난이도 : Level 2

문제링크

• 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다.
• 이를 위해 가장 스코빌 지수가 낮은 두개의 음식을 섞어 새로운 음식을 만든다.
  • 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
• 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다
• 섞어야 하는 최소 횟수를 리턴하라

 

해설

1. 최소힙을 사용하여 가장 스코빌 지수가 낮은 음식 두개를 꺼냅니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int s : scoville) {
    pq.add(s);
}

while (pq.size() > 1 && pq.peek() < K) {
    int min = pq.poll();
    int min2 = pq.poll();            
    pq.offer(min + min2*2);
    answer++;
}

• 가장 스코빌 지수가 작은 음식이 K보다 작은지 확인합니다.
• 꺼낼 음식의 갯수가 2개이상인지 확인합니다.

 

2. 모든 섞기 연산 후의 음식의 스코빌 지수를 확인합니다.

if (pq.peek() < K) {
    return -1;
}

return answer;

• 모든 섞기 연산 후에도 스코빌 지수가 K 미만이면 -1 을 반환합니다.
• 섞은 횟수를 리턴합니다.