[PS] 99클럽 코테 스터디 9일차 TIL (더 맵게)

문제

문제 링크

풀이

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int j : scoville) {
            minHeap.add(j);
        }

        return getInteger(minHeap, K);

    }

    private Integer getInteger(PriorityQueue<Integer> minHeap, int K) {
        int count = 0;

        while (minHeap.peek() < K) {
            // 1
            if (minHeap.size() <= 1) {
                count = -1;
                break;
            }
            Integer firstMin = minHeap.poll();
            Integer secondMin = minHeap.poll();
            int newScoville = firstMin + (secondMin * 2);
            // 2
            minHeap.add(newScoville);
            count++;

        }
        return count;

    }
}

문제에서 작은 요소를 계속해서 뽑아내 계산하는 조건이 있기때문에 우선순위 큐(Heap) 을 사용하기에 좋아 보인다. 초기 입력 배열을 모두 Heap 에 넣으면 이후 poll() 로 꺼낼때마다 최소값이 꺼내지기 때문에 편리하다. (만약 최소힙이 아니라 최대힙이 필요하다면 new PriorityQueue<>(Comparator.reverseOrder()) 이런 식으로 Comparator 타입의 정렬 조건을 두번째 인자로 넣어주면 된다.)

먼저 스코빌 지수를 재계산 해서 다시 힙으로 계속해서 넣어주는 작업이 필요하다. 2번 주석에서 그 역할을 하고 있다. 그 후 작업 횟수를 1 증가시켜 준 뒤 다시 while 문 조건을 확인하게 된다. 최소힙에서 minHeap.peek() 은 항상 최소값을 반환하기 때문에 문제에서 요구하는 모든 항목이 K 보다 커야 된다 는 것은 최소값이 K 보다 크다면 나머지 항목은 볼 필요 없게된다.

단지 힙에서 꺼낸 그 값만 가지고 조건을 만들 수 있어 코드가 간결해 진다.

만약 우선순위 큐가 아닌 ArrayList 나 배열로 풀게되면 정렬 하는 작업을 추가로 해야된다.

while 문을 충분히 돌고나면 힙의 항목이 계속 줄어들어 결국 저 계산식을 수행할 만큼의 항목도 남지 않게 될 것이다. 그 조건이 1번 주석에 해당한다. 힙의 항목이 1개 이하로 떨어지게 되면 더이상 newScoville 값을 만들 수 없기 때문에 문제에서 요구하는 -1 을 리턴해줘야 한다.