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

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

접근

처음에는 최소 값 두개를 추출하고 조합하여 추가한뒤 다시 정렬을 함으로써

순서를 보장하는 방식을 취했다.

그러나 프로그래머스의 효율성 테스트를 통과하지 못했고

다른 풀이들을 보면서 효율성을 따져보았다.

 

public int solution(int[] scoville, int K) {
        if(K == 0) return 0;

        int count = 0;
        // 정렬이 반드시 필요한 상황이다.
        PriorityQueue<Integer> list = new PriorityQueue<Integer>();
        for(int i : scoville){
            list.add(i);
        }
        Collections.sort(list);

        while(list.size() > 1){
            count ++;
            int mixed = list.get(0) + list.get(1)*2;
            list.remove(0);
            list.remove(0);
            list.add(0 , mixed);
            Collections.sort(list);
            if(list.get(0) >= K){
                break;
            }
        }
        if(list.get(0) >= K){
            return count;
        }else{
            return -1;
        }
    }

 

java 에서의 sort 는 고급 정렬로서 O(n log n) 의 시간 복잡도를 갖는다. while 문 안에 있기에 최종적으로는 O( n^2 * log n ) 을 가지게 된다.

 

그러나 해당 정렬을 매번 사용하지 않고 최소힙을 이용하면 고급 정렬의 시간 복잡도 대신 힙의 추가 삭제 시간 복잡도인 log n 을 사용할 수 있기에 최종적으로 O(n log n) 의 시간 복잡도로 줄어들 수 있다. 힙 정렬 또한 다른 고급 정렬과 마찬가지로 O(n log n)의 시간복잡도를 갖지만 위 구현에서는 힙정렬이 아닌 추가 삭제만 반복해서 일어나는 상황이기때문에 추가 삭제 시간복잡도 O( log n )을 적용 할 수 있었다.

 

힙(priorityQueue)을 이용한 구현은 아래와 같다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.*;

class Solution {
    
    public int solution(int[] scoville, int K) {
    if(K == 0) return 0;
        
    int count = 0;        

    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
    for(int i : scoville){
        heap.add(i);
    }
        
    while(heap.size() > 1){
        count ++;
        int first = heap.poll();
        int second = heap.poll();         
        int mixed = first + second*2;
        heap.add( mixed);
        if(heap.peek() >= K){
            break;
        }
    }
        if(heap.peek() >= K){
            return count;
        }else{
            return -1;
        }
}
    public void printList(ArrayList<Integer> list ){
        for(int a : list){
            System.out.println(a);
        }
          System.out.println();
    }
    
}

 

 

참고로  자바에서 최대힙은 다음과 같이 구현한다.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());