[프로그래머스 Level2] 더 맵게 (JAVA)

[문제]

출처 - https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 

코딩테스트 연습 - 더 맵게

---

[문제 풀이]

이 문제의 핵심은 '우선순위 큐' 입니다.

우선순위 큐는 아직 포스팅을 안해서 간단하게 설명하면 보통의 큐처럼 동작하지만 '우선순위' 속성을 갖습니다.

새 요소에 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 갖는 요소부터 빠져나오도록 합니다.

 

그래서 이문제는 왜 우선순위 큐를 사용하는가?

 

스코빌 지수가 낮은 두 음식을 섞고 모든 음식이 주어진 K 보다 스코빌 지수가 높아야 한다.

예를들어 5, 3, 9 ,10 ,12 음식이 있으면 K = 7 보다 높아야 한다 할 때

가장 낮은 두 음식 3, 5 를 섞으면 13이 된다. 그러면 만들어진 이 지수가 어딘가 들어가서 저장이 되고 또 그 전체가 스코빌지수가 낮은 순으로 정렬이 되어야 하는데 우선순위 큐를 사용하면 힙(heap) 구조로 삽입과 삭제를 logn 으로 처리 할 수 있다.

 

스코빌지수가 주어진 배열을 우선순위 큐에 삽입하고 제거를 하면서 스코빌 지수를 계산하고 큐에 넣고 문제의 조건을 잘 지키면 해결 할 수 있습니다. 

• 우선순위 큐에 문제에 주어진 배열을 큐에 삽입한다.
• while문을 돌면서 큐의 사이즈가 1보다 클때 두개의 요소를 뽑는다. 
• 뽑은 두 요소가 문제에 주어진 K보다 크면 모든 스코빌 지수는 K보다 크기 때문에 종료를 하고 정답을 반환한다.
• 그렇지 않으면 두 요소를 섞고( a + (b*2)) 우선순위 큐에 넣는다.
• 만약 우선순위 큐가 1보다 크지 않을 경우 요소가 K보다 큰지 작은지 판단하여 정답 or -1 을 출력한다.

 

---

[소스 코드]

 

import java.util.*;

class Solution {

    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> q = new PriorityQueue<Integer>();

        for (int i = 0; i < scoville.length; i++) {
            q.add(scoville[i]);
        }

        while (true) {

            if (q.size() > 1) {
                int temp1 = q.poll();
                int temp2 = q.poll();

                if (temp1 >= K && temp2 >= K) {
                    return answer;
                }

                q.add(temp1 + (temp2 * 2));

                answer++;
            } else {
                return q.poll() >= K ? answer : -1;
            }
        }
    }
}