[JAVA] 프로그래머스 Level2. 더 맵게

[Level2] 프로세스

프로그래머스

 

문제 이해

슈도 코드

scoville 배열 -> 우선순위 큐
int count = 0;
scoville.peek() >= k -> return count;
반복:
	오름차순 정렬
	count++;
	scoville.poll() + (scoville.poll() * 2) >= k
	-> break;
	else scoville.add();


// GPT
1. 우선순위 큐(PriorityQueue)를 생성하고 scoville 배열의 모든 원소를 추가한다.
2. count(섞은 횟수)를 0으로 초기화한다.
3. 만약 최솟값(큐의 peek)이 K 이상이면 count를 반환하고 종료한다.
4. 반복문 시작 (큐의 크기가 2 이상일 동안 반복):
    4.1. count를 1 증가시킨다.
    4.2. 가장 작은 값(첫 번째 poll)과 두 번째로 작은 값(두 번째 poll)을 꺼낸다.
    4.3. 두 개의 값을 섞어서 새로운 값을 만든다: newScoville = first + (second * 2)
    4.4. 만약 newScoville이 K 이상이면 count를 반환하고 종료한다.
    4.5. 그렇지 않으면 newScoville을 큐에 추가한다.
5. 반복이 끝난 후, 남아있는 값이 K 이상이면 count를 반환하고, 그렇지 않으면 -1을 반환한다.

참고한 부분

// 변경 전 (몇 개의 테스트케이스 실패)
if (sc < K) pQueue.add(sc);
// 변경 후
pQueue.add(sc);

// -> K 미만일 경우에만 우선순위 큐에 다시 추가하는 게 아니라 무조건 추가해야 함.

전체 코드

import java.util.*;

class Solution {
    public long solution(int[] scoville, int K) {
        long answer = 0;
        PriorityQueue<Integer> pQueue = new PriorityQueue<>();
        for (int s: scoville) {
            pQueue.add(s);
        }
        
        while (pQueue.size() > 1) {
            if (pQueue.peek() >= K) return answer;
            int sc = pQueue.poll() + (pQueue.poll() * 2);
            pQueue.add(sc);
            answer++;
        }
        
        if (!pQueue.isEmpty() && pQueue.peek() < K) {
            answer = -1;
        }
        return answer;
    }
}