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

코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 더 맵게

문제해석

문제를 해결하는데 있어 가장 먼저 생각난 것은 '정렬'입니다.

새로운 음식을 만들어 내는데 스코빌 지수가 가장 작은 2개가 사용되기 때문입니다.

작은 순으로 정렬이 이루어지는 것으로 Min Heap이 떠올랐습니다.

우선순위 큐(Priority Queue)는 Heap으로 구현된 우선순위에 따라 순서가 결정되는 Queue입니다.

직접 함수를 통해 sort를 수행하려 하지 않아도 큐에 원소가 추가될 때 입력된 값에 따라 정렬이 이루어지므로 

새로운 음식을 만들고 난 후 사용된 2개의 음식은 제거되므로 값이 작은 순으로 큐에서 꺼내고 두 음식의 스코빌지수로 계산된 새로운 음식의 스코빌 지수를 우선순위 큐에 삽입함으로서 문제는 간단하게 해결될 것입니다.

풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> priorityqueue = new PriorityQueue<>();
        for(var element : scoville){
            priorityqueue.add(element);
        }
        while(priorityqueue.peek() < K){
            if(priorityqueue.size()<2) return -1;
            int leastspicy = priorityqueue.poll();
            int secondlyleastspicy = priorityqueue.poll();
            priorityqueue.add(mix(leastspicy,secondlyleastspicy));
            answer++;
        }
        
        return answer;
    }
    public int mix(int a, int b){
           return a+(b*2);
    }
}

Priority Queue로 문제를 해결하는 코드를 작성하였습니다.

초기 입력된 배열의 값들을 Priority Queue에 입력하는 과정에서 사용된 var은 컴파일러가 지역 변수의 타입을 추론하도록 허용하는 키워드입니다.

이미 타입이 명시된 int 형 배열 scoville이기 때문에 원소의 타입도 int형임을 쉽게 알 수 있으므로 var로 간결하게 표현하였습니다.

문제가 해결되었는지의 판단에 대해서 Priority Queue의 첫번째 원소의 값을 최소값입니다.

최소값이 목표로 하는 스코빌 지수 K보다 크거나 같다면 다른 원소들도 K보다 같음을 알 수 있습니다.

문제를 해결할 수 없는 입력이 주어졌을 경우 새로운 음식을 계속 만들다가 Priority Queue에 원소가 1개 밖에 남지 않았을 때 2개의 원소를 꺼내려는 시도에 의해 런타임 에러가 발생합니다.

따라서 Priority Queue의 크기가 2보다 작다면 -1을 리턴하는 방식으로 문제를 해결하였습니다.

우선순위 큐(Priority Queue)와 힙(Heap)

Priority Queue는 왜 Queue가 아닌 Heap으로 구현된 자료구조일까요?

그 이유는 우선순위가 작은 순서대로 나가야 하는 '정렬'이 필요한 자료구조이기 때문입니다.

Queue는 FIFO(First In, First Out)의 목적을 가지고 구현되어 있으며 Array 또는 LinkedList로 큐 메모리 구조를 구현할 수 있습니다.

 

Priority Queue의 고려하여 구현하여야 할 기능은 다음과 같습니다.

1. 삭제

우선순위 큐도 큐와 동일하게 첫번째 원소만이 삭제됩니다.

Heap에서 첫번째 원소의 삭제시 가장 마지막 원소가 첫번째 원소로 이동하고, 규칙을 만족할 때까지 부모-자식간의 교환이 이루어집니다. 따라서 Heap의 높이인 O( log2(n) )의 시간복잡도를 갖습니다.

Array나 LinkedList에서는 첫번째 메모리 주소를 반환하고 다음 원소의 메모리 주소로 큐의 주소를 이동시키면 됩니다.

시간복잡도 O(1)로 구현될 수 있으므로 삭제에 대해서는 더 빠르다고 볼 수 있습니다.

 

2. 삽입

삽입의 구현에 있어 Array와 LinkedList는 Heap보다 비효율적입니다.

Heap은 마지막 원소로 추가된 이후 부모-자식 간의 대소 비교만을 통해 최소/최대 값을 찾을 수 있습니다.

O( log2(n) )의 시간복잡도를 갖습니다.

그러나 Array와 LinkedList는 원소의 삽입시 우선순위에 맞는 위치에 원소가 있어야 하는데, 이미 원소가 있는 경우 다음 메모리 위치로 이동을 해야하고 결국 마지막 원소 위치까지 반복이 됩니다.

최악의 경우는 우선순위 큐에 있던 최소값보다 작은 값의 원소가 삽입되는 경우이며 이때 삽입에 소요되는 시간은 O(n)입니다.

 

삭제와 삽입에 드는 시간적 비용의 편차가 덜하고 효율적이므로 Heap이 우선순위 큐의 구현에 선택된 것입니다.

 

java에서 Priority Queue는 클래스, Queue는 인터페이스입니다.

일반적으로 Queue 인터페이스는 LinkedList를 사용하여 구현하고 있습니다. 

Queue의 함수(add, element, offer, peek, poll, remove)를 우선순위 없이 구현하기에 LinkedList가 효율적이기 때문입니다.

그러나 Priority Queue는 앞서 말한 기능들을 우선순위를 지키도록 구현하기에 Heap이 보다 더 효율적이었다라고 이해하시면 되겠습니다.