[Heap] 더 맵게 - Java 코드

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

코딩테스트 연습 - 더 맵게

 

문제

 

이해

정렬의 개념이 필요하다.

Heap (PriortyQueue) 자료구조에 들어가므로 오름차순 정렬되는 특성을 이용하여

매개변수로 받는 스코빌지수가 정렬되면,

첫번째 원소(peek)가 K를 만족하는지 체크하면서

poll()  를 통해  가장 맵지 않은 두 원소를 차례로 빼서 새로운 조합을 다시 힙에 넣어주며 풀면 된다.

 

풀이

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        // 우선순위큐 초기화
        for(int i : scoville)
            pq.add(i);
        int result,count=0;
        // 2개를 하나로 만듬
        while(pq.size()>1) { // 2개 이상인 경우만 가능하므로
            if(pq.peek() >= K) // 제일작은값이 k를 넘으면 종료
                return count;
            pq.add(pq.poll() + (pq.poll()*2));
            count++;
        }
        if(pq.peek() >= K)
            return count;

        // 다 섞어도 제일 작은값이 k를 못넘으면
        return -1;
    }
}

 

Heap 자료구조에 첫문제라 쉬운난이도 였지만,

메모리의 힙(Heap) 영역과 같은 용어를 사용하기 때문에

우선순위큐를 의미상의 혼동하지 않길 바란다.