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

🔗 문제 링크

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

👨🏻‍💻 처음 작성한 코드 (런타임 에러 발생)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int temp1;
        int temp2;
        
        List<Integer> list = new LinkedList<>();
        
        for (int i: scoville)
            list.add(i);
        
        Collections.sort(list);
        
        while ((list.get(0) < K) || (list.get(1) < K)) {
            temp1 = list.remove(0);
            temp2 = list.remove(0);
            list.add(0, temp1 + (temp2*2));
            answer++;
        }
        
        if(list.get(0) < K)
            return -1;
        
        return answer;
    }
    
}

👨🏻‍💻 PriorityQueue로 작성한 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int temp1;
        int temp2;
        
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
        for (int i: scoville)
            queue.offer(i);
        
        while (queue.peek() < K) {
            if (queue.size() == 1) return -1;
            temp1 = queue.poll();
            temp2 = queue.poll();
            queue.offer(temp1 + (temp2*2));
            answer++;
        }
        
        if(queue.peek() < K)
            return -1;
   
        return answer;
    }
}

📝 결론

이번 문제는 Heap을 사용하여 해결을 하는 문제였다.
처음에는 LinkedList class를 사용하여 문제를 해결하려고 하였으나 logic은 맞으나 코드의 효율이 떨어져 채점하기에서 모든 문제가 runtime error가 발생하였다.

그래서 실행시간을 줄이기 위해 내부 구조가 Heap구조로 동작하여 자동으로 sort가 되는 PriorityQueue를 사용하여 문제를 해결하였다.

PriorityQueue는 내부구조가 Heap구조로 구성되어 있기에 시간 복잡도는 O(NLogN)으로 이번 문제와 같이 Heap을 사용하여 풀어야 하는 문제에 사용하기 좋다.