더 맵게 문제 요약

• 프로그래머스 더 맵게 문제 링크
• int 배열 scoville과 int K를 받은 뒤
  • 배열 안에 K값 보다 작은 값이 있다면 가장 작은 값 + (두 번째로 가장 작은 값 * 2)를 해서 배열에 추가해야 한다
  • 위 계산을 수행한 횟수를 Return
  • 계산을 계속 진행해도 K 이상 만들 수 없다면 -1 Return

더 맵게 풀이방법 (자바)

문제 내용을 보면 대량의 데이터를 삽입하면서 또 정렬이 필요하기 때문에 List를 활용해 숫자 더하고 정렬하다 보면 시간이 지나치게 오래 걸리므로 데이터 삽입 시 자동 정렬을 해 주는 우선순위 큐를 사용하면 시간 복잡도가 O(log n)으로 동작하여 대량의 데이터 삽입에도 효율적인 처리가 가능하게 된다.

// 프로그래머스 더 맵게
// https://school.programmers.co.kr/learn/courses/30/lessons/42626
public class MoreHotter {

    public static int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i : scoville) {
            priorityQueue.offer(i);
        }

        while(priorityQueue.peek() < K) {
            if(priorityQueue.size() < 2) { // Queue의 크기가 1이 되었으면 뭘 해도 K보다 작음
                return -1;
            }
            priorityQueue.offer(priorityQueue.poll() + (priorityQueue.poll() * 2));
            answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 9, 10, 12};
        System.out.println(solution(arr, 7));
    }

}

코드를 통해 알아보자면 먼저 PriorityQueue를 선언하고 int 배열로 받은 scoville을 모두 넣어주면 자동으로 오름차순(낮은 값이 큐에서 먼저 뽑힘) 정렬이 되고 이후에는 큐에서 값을 뽑아주면 가장 낮은 값 순으로 뽑히게 되는데 가장 낮은 값이 K 미만이라면 큐에서 한번 더 값을 뽑아주면 두 번째로 낮은 값을 뽑을 수 있으므로

가장 작은 값 + (두 번째로 낮은 값 * 2) 를 진행하면 두 값이 자동으로 큐에서 빠지고 더한 값을 넣어주면 따로 정렬을 할 필요 없이 PriorityQueue에 의해서 자동 정렬이 진행되고 반복을 계속 돌리다 보면 K보다 낮은 수를 모두 없애면서 계산을 진행한 횟수를 쉽게 구할 수 있다.

주의해야 할 점은 위 계산을 수행해도 K보다 높아지지 못하는 경우가 있다는 건데, 이는 반복문을 수행하면서 큐 사이즈가 2 미만이면 큐에 하나밖에 없다면 이 말은 이전에 계산을 수행했음에도 K보다 높아지지 못했다는 말이기 때문에 이 경우에만 -1을 리턴해주면 된다.

그리고 핵심적인 내용 외에 for 안에 계속 if문을 넣기 시작하면 시간이 그에 비례해 증가하기 때문에 최대한 단순한 구조로 가는 것이 테스트 시간을 줄이는 방법이다.