[프로그래머스] 더 맵게

---

프로그래머스 Lv2 - 더 맵게 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 힙 문제 중 레벨 2 더 맵게 문제를 풀이했다.

힙 자료구조로 구현한 자바의 우선순위 큐 클래스를 통해 풀이하였다.
문제를 풀이하면서 두 가지 문제점이 있었는데
1. 도대체 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우가 어딨지?
2. 제일 낮은 스코빌 지수 음식을 뽑아보면 두 개 다 K보다 작겠지라는 생각

1번 문제의 경우 생각을 해보니 현재 큐에 존재하는 K보다 스코빌 지수가 낮은 음식들을 뽑고 섞다보면, 섞기위한 음식 두 개가 아닌 하나의 음식만 남게될 경우가 있겠구나 라고 판단하였고 if(nextLowScoville ==null) 조건을 추가했다.

2번 문제의 경우 잘못된 생각을 해서 해맨 부분으로, 만약 제일 스코빌 지수가 낮은 두 음식의 스코빌 지수가 2, 9 이고 K가 7이라면 2의 스코빌 지수를 가진 음식만 K보다 낮지만 어찌됐든 2를 K보다 높이기 위해 9 스코빌 지수를 가진 음식과 섞어 20을 만들어야 한다는 부분이 누락되었었다.
결론적으로 조건 하나를 뺐다.

변경 전

if(nextLowScoville < K) {
	Integer mixedScoville = lowScoville + (nextLowScoville * 2);
	pq.add(mixedScoville);
	answer++;
}

변경 후

Integer mixedScoville = lowScoville + (nextLowScoville * 2);
pq.add(mixedScoville);
answer++;

최종 풀이 로직은 아래와 같다.

MoreSpicy.java

package com.example.Programmers.Lv2;

import java.util.PriorityQueue;

/**
 * 프로그래머스 Lv2 - 더 맵게
 * 힙 자료구조를 구현한 우선순위 큐 클래스를 통한 풀이
 */
public class MoreSpicy {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 우선순위 큐 초기화
        for (int i = 0; i < scoville.length; i++) {
            pq.add(scoville[i]);
        }

        // 큐가 빌 때까지 반복
        while (!pq.isEmpty()) {
            Integer lowScoville = pq.poll();
            if (lowScoville < K) {
                Integer nextLowScoville = pq.poll();
                // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우(섞기위한 다음 음식이 없을 떄)
                if (nextLowScoville == null) {
                    return -1;
                }
                Integer mixedScoville = lowScoville + (nextLowScoville * 2);
                pq.add(mixedScoville);
                answer++;
            }
        }

        return answer;
    }
}

MoreSpicyTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class MoreSpicyTest {
    @Test
    public void testMoreSpicy() {
        MoreSpicy m = new MoreSpicy();

        int result1 = m.solution(new int[] { 1, 2, 3, 9, 10, 12 }, 7);

        assertEquals(2, result1);
    }
}