프로그래머스 | LV.2 더 맵게 - 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 더 맵게 - 구현 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

가장 처음에는 scoville[] 배열 안에서 K보다 작은 값들만 뽑아서 처리하면 된다고 생각했고, 매번 가장 작은 값과 가장 큰 값을 섞는 게 최선이라 생각했다. 하지만 둘 다 아니었다.

아마도 생각하건데, 작은값들끼리만 계산하는 것은 그 값이 1개일 때 무조건 불가능하다고 처리될텐데 모든 음식을 섞을 수 있기 때문에 그렇게 처리할 경우 엣지 케이스가 많고,

매번 가장 작은 값과 가장 큰 값을 섞는다면 매번 큰 값과 섞인 1개의 작은 값이 '확실하게  K이상은 되겠지만', 1개씩 K이상을 만드는 처리보다는, 작은 두 개의 값을 합쳐서 2개의 작은 값이 (항상은 아니겠지만) K이상 되도록 처리하는 것이 더 적게 섞는 방법이 된다.

결국 pQ를 활용하여 맨 앞의 두 값에 대해 섞고 다음 처리를 반복하고

반복 끝에 pQ에 남은 값이 1개인데 그 값조차 K 미만일 경우는 [불가능]한 것으로 판단하여 -1을 리턴하고, 그렇지 않다면 그때의 answer를 리턴하면 된다.

 

1) PQ에 모든 scoville 값을 담고 자동 오름차순 배열을 정렬한다.

2) while문을 돌면서 pQ에서 가장 상단에 위치한 값이 K보다 작은 동안 반복할 건데,

- 그럼에도 pQ 사이즈가 1개만 남는 경우 -1을 리턴 (불가능한 케이스이므로)

- 그렇지 않다면 매번 앞에서 두 가지 값을 뽑아서 음식 섞고 pQ에 다시 담으면서 연산++처리

3) 이렇게 연산된 결과가 최소로 음식 섞어서 K이상의 음식을 만드는 경우가 된다.

---

💚 제출 코드

import java.util.*;

class Solution {
    //솔루션 함수 
    public int solution(int[] scoville, int K) {
        int answer = 0;
    
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        
        for(int x : scoville){
            pQ.offer(x);
        }
        
        while(pQ.peek() < K){
            if(pQ.size() >= 2){
                pQ.offer(pQ.poll()  + (pQ.poll()) * 2);
                answer++;
            }else{
                return -1;
            }
        }
    
        return answer;
    }
}