[프로그래머스 | Java Lv.2] 더 맵게

문제

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

 

힙 정렬을 사용해야하는 걸 알면 쉬웠던 문제..! 

자바에서 힙 정렬 = PriorityQueue 임을 잊지 말기

 

PriorityQueue 선언 방법

import java.util.*;

PriorityQueue<Integer> pq = new PriorityQueue();

 

---

첫 번째  코드 - 실패

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue();
        
        for(int i : scoville){
            pq.add(i);
        }
        
        // System.out.println(pq);
        
        Integer a, b;
        while(pq.peek() < K){
            a = pq.remove();
            b = pq.remove();
            
            pq.add(a + 2*b);
            
            answer++;
            
        }
        
        return answer;
    }
}

 

실행 결과 

 

실행을 했을 때 몇 가지 테스트 케이스만 실패된다면 범위나 제한 조건을 보면 대부분 답이 나온다.

내가 놓쳤던 제한 사항은 아래 케이스

 

while문의 조건을 다음과 같이 수정, -1 반환 조건 추가

   while(pq.peek() < K && pq.size() >= 2){
     ..
   }
   
//우선순위 큐에 한 개만 남았고, 그게 K보다도 작으면 불가능 => -1 return
if(pq.size() == 1 && pq.peek() < K) return -1;

 

최종 코드 - 성공

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue();
        
        for(int i : scoville){
            pq.offer(i);
        }
        
        // System.out.println(pq);
        
        Integer a, b;
        // 우선순위 큐의 가장 앞이 K보다 작을 때 계속 반복하되, 큐의 원소가 2개일 때까지만 반복
        while(pq.peek() < K && pq.size() >= 2){
            if(pq.peek() < K) {
                a = pq.remove();
                b = pq.remove();
                pq.add(a + 2*b);
            
                answer++;
            }   
        }
        
        //우선순위 큐에 한 개만 남았고, 그게 K보다도 작으면 불가능 => -1 return
        if(pq.size() == 1 && pq.peek() < K) return -1;
        
        else return answer;
    }
}