프로그래머스) - 더 맵게 (우선순위 큐)

문제 출처 입니다.

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

프로그래머스

 

 

 

나의 풀이

몇일동안 잡고 끙끙대면서 노력했지만 아무래도 왜 틀렸는데 이해가 안된다. 왜 틀렸는지 언젠가는 발견할 수 있으면 좋겠다. 

(↓오답 풀이입니다....ㅠㅠ)

 

import java.util.*;
 
class Test {
    public int solution(int[] scoville, int K) {
         
        int answer=0;
        int result=0;
       
        while(true){ 
            Arrays.sort(scoville);
            result=scoville[0]+(scoville[1]*2);
            answer++;
            System.out.println("result :"+result);
            for(int i=0;i<scoville.length;i++){System.out.println("원래의 스코빌["+i+"]"+scoville[i]);}
            if(result<K){
                for(int i=0;i<scoville.length-1;i++){
                    scoville[i]=scoville[i+1];
                }
                scoville[0]=result;
                for(int j=0;j<scoville.length;j++){System.out.println("array전의 스코빌["+j+"]"+scoville[j]);}
                scoville = Arrays.copyOf(scoville, scoville.length-1);
                for(int i=0;i<scoville.length;i++){System.out.println("array이후의 스코빌["+i+"]"+scoville[i]);}
 
                    System.out.println("answer :"+answer);
                    continue;
            }else if (scoville.length==1) answer=-1;
            else if(result>=K) System.out.println("끝이다~~"); break;
             
        }
        return answer;
    }
}

답지 풀이

다른 사람들의 풀이를 보니 우선순위 큐(Priority Queue) 정렬로 많이 풀었다. 

우선순위 큐 정렬 풀이

import java.util.PriorityQueue;
/**
 *
 * @author HEESOO
 *
 */
 class Solution {
     public int solution(int[] scoville, int K) {
         int answer = 0;
         int a,b;
         PriorityQueue<Integer> pq=new PriorityQueue<>();
         for(int i:scoville){
             pq.offer(i);
         }
         while(pq.peek()<K){
             if(pq.size()==1){
                 return -1;
             }
             else{
                 a=pq.poll();
                 b=pq.poll();
                 pq.offer(a+(b*2));
                 answer++;
             }
         }
         return answer;
     }
 }

---

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
 
        for(int i = 0; i < scoville.length; i++)
            q.add(scoville[i]);
 
        int count = 0;
        while(q.size() > 1 && q.peek() < K){
            int weakHot = q.poll();
            int secondWeakHot = q.poll();
 
            int mixHot = weakHot + (secondWeakHot * 2);
            q.add(mixHot);
            count++;
        }
 
        if(q.size() <= 1 && q.peek() < K)
            count = -1;
 
        return count;
    }
}