프로그래머스-더 맵게

개요

이번 문제에 대한 정리는 까페에서 커피한잔 하면서 쓰게 되었다. 역시 카페인이 함께하니 글이 좀더 잘 써지는 느낌이 든다. 다소 이야기가 옆으로 빠졌는데 본론으로 들어와 이번 문제는 힙을 이용한 문제이다. 문제 자체는 그리 어려운 문제가 아니였다.

문제 링크

• 프로그래머스-더 맵게

분류

• Level 2
• 힙

요점

• 최소 힙을 이용하면 쉽게 풀린다.
• 최소 힙 특성상 모든 요소가 주어진 K를 검사할 필요 없다.
• 최소힙을 직접 구현하지 않고 PriorityQueue(우선순위 큐)를 사용.
• PriorityQueue가 힙을 사용하기 때문에 그 특성도 그대로 가져감

어려웠던 부분

• 없음

코드(javascript)

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

        int answer = 0;

        java.util.PriorityQueue<Integer> scovilleHeap = new java.util.PriorityQueue<Integer>();

        for(int scovilleLevel : scoville){

            scovilleHeap.add(scovilleLevel);

        }

        while(true){

            //힙의 요소 갯수가 0이면 -1

            if(scovilleHeap.size() == 0){

                answer = -1;

                break;

            }

            int currentLevel = scovilleHeap.peek();

            //힙에서 꺼낸 첫번재 요소가 K 이상을 만족하였다면

            //나머지 요소들도 이를 만족한다고 볼 수 있다.

            //우선순위 큐가 heap을 사용하기 때문임.

            if(currentLevel >= K){

                 break;

            }

            //요소가 하나만 남았고 7이하 값이면 더이상 K 이상의 값을 만들 수 없는 상태

            if(scovilleHeap.size() == 1 && currentLevel < K){

                answer = -1;

                break;

            }

            int first = scovilleHeap.poll();

            int second = scovilleHeap.poll();

            int newScoville = first + (second * 2);

            scovilleHeap.add(newScoville);

            answer++;

        }

        return answer;

    }

• 여기서 좀더 정리할 내용이 있다.

    peek() 함수는 큐의 내용만 확인한다.
  
    poll() 함수는 큐 내부의 요소를 제거하고 그 결과로 요소를 반환한다.
  
    최소 힙(Min Heap) : 부모 노드가 자식 노드보다 항상 작은 트리 구조를 말함.
  
    최대 힙(Max Heap) : 부모 노드가 자식 노드보다 항상 큰 트리 구조를 말함.
  

(위 문제에서는 최소 힙을 사용하여 문제를 해결하였다)