[힙] 더 맵게

프로그래머스 힙 더맵게

처음풀이

class Solution {

    static PriorityQueue<Integer> pq;

    public int solution(int[] scoville, int K) {

        pq = new PriorityQueue<>();
        for(int s: scoville){
            pq.add(s);
        }

        return shake(0, K);
    }

    public static int shake(int count, int K){

        //하나남음
        if(pq.size()==1){
            if(K<=pq.poll()) return count; //통과
            else return -1;                //나가리
        }

        //두개이상 남음
        int last1 = pq.poll();
        int last2 = pq.poll();

        if(K <= last1) return count; //통과

        pq.add(last1+last2*2);

        return shake(count+1, K);
    }

}

이것도 맞긴 한데, 데이터의 양이 커지맨 재귀가 스택에 너무 많이 쌓여서 오버플로우 난다.

수정된 풀이

package 더맵게;

import java.util.PriorityQueue;

public class Solution {

    static PriorityQueue<Integer> pq;

    public static void main(String[] args){


        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K=7;

        pq = new PriorityQueue<>();
        for(int s: scoville){
            pq.add(s);
        }

        int count = 0;
        while (true){

            //하나남음
            if(pq.size()==1){
                if(K<=pq.poll()) break; //통과
                else{
                    count = -1; //나가리
                    break;
                }
            }

            //두개이상 남음
            int last = pq.poll();
            int last2 = pq.poll();

            if(K <= last){
                break; //통과
            }

            pq.add(last+last2*2);
            count++;
        }

        System.out.println( count );
    }
}

재귀를 반복문으로 수정