[프로그래머스,Level 2] 더 맵게(JAVA 구현)

- 첫 풀이 및 정답풀이

  처음에 문제를 자세히 읽지 않고 코딩을 하는 바람에 다른 로직을 생각했지만, 다시 읽어보아 이 문제가 원하는 반환 값을 파악했다. 이 문제가 원하는 것은 데이터로 전달되는 스코빌 지수를 정해진 공식을 이용해 계산하여 모든 스코빌 지수가 K이상이 되는 최소 계산횟수이다. 또한, 주의해야 할 부분은 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 반환이라는 부분이다.

 

  우선순위 큐를 사용한다면, 전달된 스코빌 지수가 항상 가장 낮은 값을 받아올 수 있기 때문에 이를 이용한다. 이러한 특성을 이용해 peek() 메서드로 우선순위가 가장 높은 것을 참조했을 때 K보다 낮은 값이라면, 문제의 공식을 이용해 다시 큐에 넣어주는 과정을 수행한다.

---

 

  예제를 통해 살펴보면,

 

    1. 1, 2 3, 9, 10, 12를 우선순위 큐에 삽입

    2. peek() 메서드로 가장 우선순위가 높은(스코빌 지수가 가장 낮은) 값을 참조했을 때, K보다 낮다면, (K는 7)

    3. 공식에 따라 poll() + (poll() * 2) 후 add() 수행 및 계산 횟수 카운팅. (1 + 2 * 2 = 5)

    4. 3, 5, 9, 10, 12인 상태에서 2번 ~ 3번 과정을 반복.

    5. 9, 10, 12, 13인 상태가 되면, 2번 과정의 조건을 만족하지 않으므로 수행 종료 및 계산 횟수 반환.

---

 

  위의 과정은 일반적으로 데이터가 주어지는 경우에 대해서는 완벽하게 동작한다. 그러나 문제에서 주어진 것처럼 예외 상황에 대한 처리를 해주어야 한다. 모든 스코빌 지수가 K 이상이 되지 않는 경우에 대해서 말이다. 이에 대한 예제는 본인이 생각해 본 바, 스코빌 지수가 모두 0으로 주어지고 K가 1 이상인 경우가 대표적일 것이다.

 

    1. 0, 0, 0, 0인 스코빌 지수를 우선순위 큐에 삽입

    2. 위의 2 ~3번 과정 수행하면, 0, 0, 0이 되고, 한 번더 수행하면 0, 0 이후 한 번 더 수행해 0이 된다.

    3. 스코빌 지수 0만 남은 상황에서 또 한 번 수행하면, poll()이 두 번 수행되어야 하는데 데이터가 한 개뿐이라 null           이 반환된다.

    4. 이 경우 우선순위 큐에 더이상 데이터가 남지 않게 되므로, 모든 스코빌 지수를 K이상으로 만들 수 없게 된다.

    5. 따라서 위의 과정을 거쳤을 때, 우선순위 큐가 비게 된다면 계산 횟수를 -1로 반환해주면 된다.

 

---

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int sum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 1. 스코빌 지수 데이터를 우선순위 큐에 삽입.
        for(int x : scoville){
                pq.add(x);             
        }
        
        // 2. 큐가 비어있지 않고, 우선순위가 높은(스코빌 지수가 낮은) 데이터 < K인 경우,
        while(!pq.isEmpty() && pq.peek() < K){
            // 3. 두 데이터를 poll(), null 체크를 위해 Wrapper클래스를 이용.
            Integer a = pq.poll();
            Integer b = pq.poll();
            
            // 4. 만약 두 데이터 중 하나라도 null이 존재한다면 더 이상 아래 연산이 불가능하므로 break.
            if(a == null || b == null) break;
            
            // 5. 문제에서 제공하는 공식.
            sum = a + (b * 2);
            // 6. 결과를 우선순위 큐에 삽입.
            pq.add(sum);
            // 7. 계산횟수 증가.
            answer++;            
        }
        
        // 8. 큐가 비었다면, 모든 스코빌 지수를 섞어도 K 이상이 되지 못하므로 -1 반환.
        if(pq.isEmpty()) return -1;
        
        return answer;
    }
}