[Algo]프로그래머스 더 맵게 in Java

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
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 합니다.

접근

간단하게 처음에는 Queue를 생성하여 정렬 한다음 가장 앞 두개를 뽑아서 섞은 다음 다시 Queue에 넣고 정렬해서 첫 번째 원소, 즉 가장 작은 값이 K 이상이면 지금까지 섞은 횟수를 반복하도록 코드를 작성하였다.

public static int solution(int[] scoville, int K) {
   int answer = 0;

   List<Integer> queue = new LinkedList<>();
   for(int i=0; i<scoville.length; i++){
      queue.add(scoville[i]);
   }
   queue.sort((a,b) -> a-b);
   while(queue.get(0) < K){
      if(queue.size() < 2) return -1;
      int f1 = queue.remove(0);
      int f2 = queue.remove(0);
      int newFood = f1 + (f2 * 2);
      queue.add(newFood);
      answer++;
      queue.sort((a,b) -> a-b);
   }

   return answer;
}

만약 음식 중에 섞어도 K 이상의 스코빌 지수를 가질 수 없으면 -1을 반환하도록 처리했고 테스트케이스는 전부 통과했지만 효율성 테스트에서 모두 실패했다. 문제 카테고리에 있는대로 Heap을 사용해야 했고 Java의 우선 순위 큐 자료구조를 사용해서 풀어야만 효율성도 통과할 수 있다.

// int[] scoville = {3,2,1,5};
public static int solution(int[] scoville, int K) {
   int answer = 0;

   PriorityQueue<Integer> heap = new PriorityQueue<>();
   for(int i=0; i<scoville.length; i++){
       heap.offer(scoville[i]);
   }
   while(!heap.isEmpty()){
       System.out.println(heap.poll());
   }
   return answer;
}

위와 같이 간단하게 우선순위 큐의 사용을 해보았다. 크기에 상관없이 넣어도 poll이나 peek 메소드를 사용하면 알아서 가장 작은 값을 가져왔다. 이렇게 하면 같은 풀이 방법으로 풀지만 sort로 의해 낭비되는 시간을 줄일 수 있었다.
정답 코드는 아래와 같다.

public int solution(int[] scoville, int K) {
   int answer = 0;

   PriorityQueue<Integer> heap = new PriorityQueue<>();
   for(int i=0; i<scoville.length; i++){
       heap.offer(scoville[i]);
   }

   while(heap.peek() < K){
       if(heap.size() < 2) return -1;
       int f1 = heap.poll();
       int f2 = heap.poll();

       int newFood = f1 + (f2 * 2);
       heap.offer(newFood);
       answer++;
   }

   return answer;
}