[프로그래머스 자바 JAVA] 더 맵게 (level 2)

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

 

 

import java.util.PriorityQueue;

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

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

        for (int i = priorityQueue.size() - 1; i >= 0; i--) {
            if(priorityQueue.size() == 1 && priorityQueue.peek() < K) {
                return -1;
            } else if(priorityQueue.peek() >= K){
                break;
            }

            int a = priorityQueue.poll();
            int b = priorityQueue.poll();
            int newScoville = a + (b * 2);
            priorityQueue.add(newScoville);

            answer++;  
        }

        return answer;
    }
}

 

 

풀이

1.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

이므로 priorityQueue(우선순위 큐)를 사용함 -> 큐에 담으면 자동적으로 우선순위대로 정렬함

 

2. 스코빌 지수가 담긴 배열을 priorityQueue에 저장함

 

3. for문을 돌리면서 섞은 음식의 스코빌 지수를 구해나가기 시작한다. (for문을 priorityQueue.size()부터 시작한 이유는

​입출력 설명에 나와있는 것처럼 scoville배열의 길이가 6부터 시작해 -> scoville.length = 5 (섞은 횟수가 1일 경우) -> scoville.length = 4 (섞은 횟수가 2일 경우) 로 점점 줄어들기 때문이다.)

 

4. 가장 맵지 않은 스코빌 지수와 두 번째로 맵지 않은 스코빌 지수를 구하기 전에 조건을 걸어준다.

     4-1. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우(priorityQueue.size()가 1일 경우 시도조차 하지 못하므로) -1을 반환한다.

     4-2. priorityQueue.peek()(우선 순위 큐의 가장 맨 앞에 있는 값 반환, 여기서 우선순위 큐의 가장 맨 앞에 있는 값은 큐 내에 존재하는 값 중 가장 작은 값을 의미한다.)가 K보다 크거나 같은 경우에 모든 음식의 스코빌 지수가 K 이상이라는 의미이므로 for문을 멈춘다.

 

5. priorityQueue.poll() : 우선순위 큐의 가장 맨 앞에 존재하는 값을 반환하고 그 값을 삭제한다. => 처음 priorityQueue.poll()을 하면 가장 맵지 않은 음식의 스코빌 지수가 반환되고 또 다시 priorityQueue.poll()를 하면 두 번째로 맵지 않은 음식의 스코빌 지수가 반환되게 된다.

 

6. 섞은 음식의 스코빌 지수를 구한 후 그 값을 우선순위 큐에 넣는다. 그리고 섞은 횟수를 +한다.