프로그래머스: 더 맵게

문제 설명

• (가장 작은 값 + 두번째로 작은 값*2)를 반복해 배열의 모든 원소가 K이상이 되도록 만드는 문제입니다.

접근법

• 가장 작은 원소를 어떻게 가져오느냐가 이 문제의 핵심입니다. 반복문으로 최소값을 찾으면 하나의 최소값을 찾는데 $O(n)$시간이, 하나를 섞을 때마다 최소값을 찾게되면 결국 $O(n^2)$시간이 소비됩니다.
• heap을 이용한 정렬은 $O(N*log2(N))$의 시간복잡도를 보장해 빠르게 최대값 혹은 최소값을 찾을 수 있습니다.
  • heap정렬을 하면 0번째 index의 값이 최대값 or 최소값이 됩니다. 0번째 값을 가져오는 상수시간은 무시될 수 있기 때문에 최소값을 구하는 시간 == heap정렬하는 시간이 됩니다.
  • heap구조는 왼쪽 혹은 오른쪽을 선택할 때마다 절반의 선택지가 줄어들기 때문에 log2시간복잡도를 가집니다.
• 우선순위 큐(Priority Queue)는 내부적으로 heap구조를 지니고 있습니다.
  • 값을 더하거나 빼더라도 항상 heap정렬이 수행된 Queue구조를 return해 줍니다.

정답

import java.util.Queue;
import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Queue<Integer> pq = new PriorityQueue(); //heap을 직접 구현하지 못할 것 같아 heap으로 구현된 우선순위 큐를 활용했습니다. 
        // 배열의 원소를 우선순위 큐에 옮겨담습니다.
        for(int i = 0; i<scoville.length;i++){
            pq.add(scoville[i]);
        } 
        // 최대 음식이 한 개가 될 때까지 섞을 수 있습니다.
        while (pq.size()>=1){
            int least_num = pq.poll(); // 가장 안매운 음식을 꺼냅니다.
            if(least_num<K){ // 가장 안매운 음식이 K보다 작다면
	    try { // pq.size()가 1인 경우 때문에 try-catch로 구현했습니다.
                    int second_num = pq.poll(); // 두 번째로 안매운 음식을 꺼내
                    int new_num = least_num + 2 * second_num; // 두 음식을 섞습니다.
                    pq.add(new_num); // 섞은 값을 다시 집어넣습니다.
                    answer++;	
	    }catch(Exception e) { // 하나의 음식이 들어왔을 때에는 더 이상 섞는게 불가능하기 때문에 -1을 return합니다
	        answer = -1;
	    } 
            }else{ // 가장 안매운 음식이 K이상이면 조건을 만족합니다.
                return answer;
            }
        }
        return -1;
    }
}