[프로그래머스] - 더 맵게

힙(Heap) 

 

모든 요소의 값이 k 이상이 될 때까지 아래의 방법을 사용해서 다시 배열에 넣어준다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 요소의 값이 k보다 커질 때 까지의 횟수를 구하는 문제! 

 

우선순위 큐에 스코빌 지수가 담긴 음식들을 넣으면 루트노드는 가장 맵지 않은 음식의 스코빌 지수 가 된다.

따라서 큐에서 값을 두개 꺼내면 해당 공식의 인자를 구할 수 있다.

두 음식을 섞어 다시 큐에 집어 넣으며 루트 노드가 K이상일 경우 or 더는 섞을 음식이 없을 경우까지 반복한다.

 

 

뽑아야 하는 것 2개(우선순위)

가장 덜 매운 음식, 그 다음으로 덜 매운 음식

 

import java.util.PriorityQueue;

class Heap {//더 맵게
    //모든 요소의 값이 k보다 커질 때 까지!의 횟수를 구하는 문제

    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>(); //우선순위 큐 선언

        for(int OneScoville : scoville){ //반복문 돌면서
            heap.offer(OneScoville); //하나씩 큐에 삽입
        }

        while (heap.peek() < K){ //반환값이 k보다 작거나 같을 경우 돌면서(반환된거지 삭제가 아님)

            if(heap.size()==1){ //scoville 길이는 2 이상인데 그 이하면
                return -1; //스코빌 지수 k 이상으로 못 만드니까 -1 리턴
            }

            //큐에서 꺼낸 값 2개 = 공식에 집어넣을 값
            int a = heap.poll();//큐 맨 앞에 있는 값 반환 후 삭제, 비어있으면 null
            int b = heap.poll();//그 다음으로 앞에 있는 값 반환 후 삭제, 비어있으면 null

            int result = a + (b * 2); //문제에서 제시한 방법

            heap.offer(result); //이거 안해도 되는건가?
            answer ++; //answer = answer + 1;
        }

        return answer;
    }
}

 

• offer() : 해당 큐 맨 뒤에 값 삽입, 성공시 true를 실패시 false를 반환
• peek() :  큐의 맨 앞에 있는 값 반환, 비어있을 경우 null 반환
• poll() : 큐 맨 앞에 있는 값 반환 후 삭제, 비어있을 경우 null 반환

 

 

횟수	가장 매운	그 다음 매운	섞은 음식 스코빌 지수	scovile
+1				1, 2, 3, 9, 10, 12
+1	1	2	1+(2*2)=5	5, 3, 9, 10, 12
	3	5	3+(5*2)=13	13, 9, 10, 12

총 횟수는 2회