[programmers] 힙_더 맵게

더 맵게

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

문제 설명
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

// 정확성 O
// 효율성 X

import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        ArrayList<Integer> scovilleList = new ArrayList<>();
        for (int sco : scoville) {
            scovilleList.add(sco);
        }
        while(scovilleList.size() > 1){
            Collections.sort(scovilleList);
            if(scovilleList.get(0)<K){
                scovilleList.set(1,scovilleList.get(0)+scovilleList.get(1)*2);
                scovilleList.remove(0);
                answer++;
            } else{
                return answer;
            }
        }
        return scovilleList.get(0)<K ? -1 : answer;
    }
}

 

// 정확성 O
// 효율성 X

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> scovillePQ = new PriorityQueue<>();
        for(int sco : scoville){
            scovillePQ.add(sco);
        }
        while(scovillePQ.size() > 1){
            int sco1 = scovillePQ.poll();
            if (sco1<K){
                scovillePQ.add(sco1+scovillePQ.poll()*2);
                answer++;
            } else{
                return answer;
            }
        }
        return scovillePQ.poll() < K ? -1 : answer;
    }
}

 

 

TIL

PriorityQueue

 

참고

 - https://kbj96.tistory.com/49