프로그래머스 - 더맵게

결과 코드와 과정출력

public static int solutionOfSpicy(int [] scoville, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Arrays.stream(scoville)
                .mapToObj(Integer::valueOf).collect(Collectors.toList()));
        int answer = 0;
        while( ! heap.isEmpty()) {

            if(heap.size() <= 1 && heap.peek() < K) {
                return -1;
            }
            Integer first = heap.poll();

            if(first < K) {
                Integer second = heap.poll();
                Integer result = first + (second * 2);
                heap.offer(result);
                answer++;
            }else {
                break;
            }
            System.out.println("heap = " + heap+", answer = " + answer);
        }

        return answer;
    }

heap = [3, 4, 3, 5, 12, 4, 9, 10], answer = 1
heap = [4, 5, 4, 9, 12, 10, 9], answer = 2
heap = [5, 9, 9, 10, 12, 12], answer = 3
heap = [9, 10, 12, 12, 23], answer = 4

 

 

문제의 설명에는 가지고있는 음식의 모든 scoville 지수가 K이상이 될때까지 첫번째와 두번째로 맵지않은 것들을 섞어 더높은 scoville지수를 만드는 문제다. 

 

음식의 scoville 지수를  높이려면 (첫번째 음식 scoville + (두번째 음식 scoville지수 * 2))를 하여 두 음식을 섞어 결과에대한 scoville지수를 가진 한가지음식을 얻을수 있다. 따라서 어떤 시점에서는 음식의 scoville 지수 랭크를 알려면 항상 정렬이 되있어야한다.

 

내림차순의 정렬을 위해 문제의 카테고리와 맞게 Heap을 사용한다. Java 에서는 Min Heap이 PriorityQueue로 구현되어 있기 때문에 아래와 같이 배열을 이용해 queue로 만들어 줄수있다.

PriorityQueue<Integer> heap = new PriorityQueue<>(Arrays.stream(scoville)
                .mapToObj(Integer::valueOf).collect(Collectors.toList()));

 

 

자세하게 설명할 순 없지만 Heap은 최댓값 또는 최솟값 구하기에 최적화 되어있는 자료구조이다. 

본론으로 넘어와서 while 문 내에 첫번째 if 문을 보게된다면, 힙 사이즈와 첫번째로 맵지않은 음식(루프를 돌며 계속 새로운 음식을 섞기때문에 첫번째가 가장 맵지않은 음식이다.) 의 scoville 지수를 판단하여 -1 을 반환한다.

 

이는 문제 설명중 "모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우에는 -1을 return 합니다." 를 의미한다.

그리고 두번째 if 문 부터 제일 낮은 scoville 지수(제일 첫번째)가 K보다 작다면 위의 섞기식을 이용해 섞고 다시 큐에 넣어준다.

 

이를 반복하고 두번째 if 문에 조건이 맞지않는다면 모든 음식의 scoville지수가 K 이상이라는 뜻이므로 음식 섞기(while 문)를 종료한다.