[프로그래머스/힙(Heap)/1] 더 맵게 (JAVA)

출처: 프로그래머스 코딩테스트 힙(Heap) 1번째 문제
(https://programmers.co.kr/learn/courses/30/lessons/42626)

문제 설명

매운 것을 좋아하는 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 합니다.

풀이 방법

1. 우선순위큐에 제공된 스코빌지수들을 넣어준다
   ( 결국 우선순위큐를 이용해 빠르게 가장 작은 값을 빼올 수 있다. )
2. 반복문 실행
3. 첫번째, 두번째로 가장 적은 스코빌 지수를 큐에서 빼낸다.
4. 두개를 섞고 다시 큐에 넣고 카운트를 증가시킨다.
5. 우선순위 큐 첫번째 데이터가 K보다 크면 반복문 종료
   ( 모든 스코빌 지수가 K 이상임을 의미)
6. 반복문이 끝나면 카운트를 반환한다.

소스 코드

import java.util.PriorityQueue;

class Solution {
    public Integer solution(int[] scoville, int K) {
        int mixCnt = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        for( int s : scoville) {
            priorityQueue.add(s);
        }

        while (priorityQueue.peek() < K ) {
            if ( priorityQueue.size() < 2 ) {
                return -1;
            }
            int firstScoville = priorityQueue.poll();
            int secondScoville = priorityQueue.poll();
            mix(priorityQueue,firstScoville,secondScoville);
            mixCnt++;
        }
        return mixCnt;
    }

    public void mix(PriorityQueue<Integer> priorityQueue,int firstScoville, int secondScoville) {
        int newScovile = firstScoville + (secondScoville * 2);
        priorityQueue.add(newScovile);
    }
}

후기

문제를 잘못 읽어서 섞는 공식을 잘못 설정해 계속 틀려서 많이 해맸다. 코딩테스트를 풀때 항상 문제를 정확히 파악하는 연습이 필요한 것 같고 반성해야겠다.