[프로그래머스] 더맵게

처음에 ArrayList로 풀었는데 정답은 맞았으나 효율성테스트에서 실패하였다.. 

import java.util.Arrays;
import java.util.ArrayList;
import java.util. Collections;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int sco=0;
        ArrayList<Integer> list=new ArrayList<Integer>();
    for (int i = 0; i < scoville.length; i++) {
	        	 list.add(scoville[i]);
			}
	    
        while(sco<=K){
            Collections.sort(list);
            sco=list.get(0)+list.get(1)*2;
            list.remove(0);
            list.remove(1);     
            answer++;
        }
      
        return answer;
    }
}

 

힙으로 풀어야 하나보다.. 

 

• PriorityQueue 선언 
• scoville 를 돌면서 큐에 넣어준다. 
• cnt는 섞은 횟수를 세는것 
• pq의 size가 1보다크고 pq의 처음값을 반환한것이 K보다 작다면 
• pq에 pq첫번째+pq두번째*2 값을 더해준다.
• poll()은 peak()과 달리 값을 반환하면서 제거됨 
• cnt++ 섞은 횟수 올리기 
• pq.peek()값이 k보다 크다면 cnt 반환 아니라면 -1반환 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
         PriorityQueue<Integer> pq = new PriorityQueue<>();
         for (int s: scoville) {
             pq.add(s);
         }

         int cnt = 0;
         while (pq.size() > 1 && pq.peek() < K) {
             pq.add(pq.poll() + pq.poll() * 2);
             cnt++;
         }

         return pq.peek() >=K? cnt :-1;
    }
}