[프로그래머스 42626번] 더 맵게

문제

내용

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

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

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

제한 사항

• 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

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

언어

JAVA

---

풀이

이번 문제는 Heap, 그 중에서도 priority queue를 이용하는 문제이다.

 

왜 Priority Queue 인가?

우선, 입력으로 들어오는 <pre>scoville</pre>를 작은 순으로 배열해야 한다.

그리고 가장 작은 원소를 연달아서 가져와야한다.

이를 위해서는 Min heap을 이용하는 것이 가장 효율적이라 생각하였다. 시간복잡도 측면에서도, 코드를 구성하는 측면에서도 말이다.

 

문제 해결

문제를 해결하는 방법은 간단하다.

1. <pre>scoville</pre>를 가장 작은 순서대로 배열한다.
2. 가장 작은 원소가 K보다 작은지 판별한다.
3. 만약 K보다 작다면 가장 작은 원소 2개를 뽑아서 섞은 후(계산한 후) 배열에 넣고, 작은 순서대로 재배열한다.
4. 만약 가장 작은 원소가 K보다 같거나 크다면 문제가 끝난다.
5. 문제를 해결할 수 없는 경우는 -1을 return한다.
   이 경우는 가장 작은 원소가 K보다 작지만, 가장 작은 원소 2개를 뽑을 수 없는 경우이다.
   즉, 가장 작은 원소가 K보다 작고, 배열의 원소 개수가 1인(2보다 작은) 경우이다.

순서도

 

코드 설명

우선, 반복문을 통해서 input으로 들어온 <pre>scoville</pre>를 PriorityQueue에 담는다.

Priority queue의 선언 시 정렬에 관한 조건이 없었기 때문에 기본적으로 오름차순(작은 것 → 큰 것)으로 정렬된다.

 

이후 <pre>while</pre> 반복문을 통해서 가장 priority queue의 가장 작은 원소가 K보다 클 때까지 <pre>섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)</pre> 연산을 실시한다.

이를 위해 조건으로 <pre>scovilles.peek() < K</pre>을 사용하였다. priority queue에서 <pre>peek()</pre>는 가장 작은 원소를 반환한다.

 

반복문 안에서 연산 과정을 수행하는데에도 조건이 필요하다.

만약 힙에서 2가지 원소를 뽑지 못한다면 진행하지 못하기 때문이다. 이 경우 문제에서는 -1을 반환하라고 지시하였다.

2가지 원소를 뽑지 못한다는 것은 크기가 1인 경우이므로, <pre>if(scovilles.size() > 1)</pre>을 통하여서 판별한다.

 

크기가 1보다 크다면 연산할 수 있는 것이므로 <pre>low1 + (low2 * 2)</pre>을 계산한 후 힙에 추가한다.

그리고 도출해야 하는 연산 횟수를 증가시킨다.

 

만약 모든 원소를 K 이상으로 만들지 못한다면 반복문 안에서 -1을 반환한다.

반복문이 끝났다는 것은 모든 원소가 K 이상이라는 의미이므로 연산횟수인 <pre>answer</pre>을 반환한다.

 

---

코드

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> scovilles = new PriorityQueue<>();

        for(int j : scoville) {
            scovilles.add(j);
        }

        while(scovilles.peek() < K) {
            if(scovilles.size() > 1) {
                int low1 = scovilles.remove();
                int low2 = scovilles.remove();

                scovilles.add(low1 + (low2 * 2));
                answer++;
            }
            else {
                return -1;
            }
        }

        return answer;
    }
}