99클럽 코테 스터디 5일차 TIL [프로그래머스] 더 맵게 (Java)

문제

[프로그래머스] 더 맵게

틀린 코드

import java.util.*;

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

틀린 이유

• 정확성 테스트는 통과했으나, 효율성 테스트에서 시간 초과가 발생했다.
• 매번 배열을 정렬해 최솟값을 구하는 것은 비효율적이다.
• 효율성을 위해 우선순위 큐(최소 힙)을 사용해 풀어야 한다.

풀이

• scoville의 값을 minHeap에 추가한다.
• poll() 메서드를 사용해 최솟값을 힙에서 삭제해 섞어준 후 다시 힙에 추가한다.
  • 섞은 횟수 answer 증가
• 최소값이 K보다 작은 동안 반복한다.
  • peek() 메서드를 활용해 최솟값을K와 비교
• 힙의 크기가 1이라면 더 이상 섞을 수 없어 스코빌 지수 K 이상의 음식을 만들 수 없으므로 -1을 리턴한다.

정답 코드

import java.util.*;

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