연결 리스트 관련 문제를 풀다가 우선순위 큐를 접하게 되었다.
23. Merge k Sorted Lists
해당 문제는 k개의 서로 다른 노드 개수를 가진 연결 리스트들을 모두 오름차순 순으로 정렬하는 문제이다.
나는 단순하게 연결 리스트를 순회하면서 하나씩 병합하고자 했다.
k가 최대 10^4개까지 가능하기 때문에 index 별로 비교하는 것 보다 연결 리스트를 차례로 방문하는 것이 더 빠르다고 생각했다.
병합 과정은 연결 리스트 병합과 동일하게 진행하였다.
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode head = null;
if(k < 1) return head;
for(int i = 0; i < k; i++){
// 빈 값에 대한 예외 처리
head = mergedList(head, lists[i]);
}
return head;
}
public ListNode mergedList(ListNode mergedNode, ListNode nowNode){
if(mergedNode == null) return nowNode;
if(nowNode == null) return mergedNode;
ListNode dump = new ListNode(0);
ListNode current = dump;
while(mergedNode != null && nowNode != null){
if(mergedNode.val > nowNode.val){
current.next = nowNode;
nowNode = nowNode.next;
}
else{
current.next = mergedNode;
mergedNode = mergedNode.next;
}
current = current.next;
current.next = null;
}
if(mergedNode == null) current.next = nowNode;
else if(nowNode == null) current.next = mergedNode;
return dump.next;
}
}88ms에 44.22mb의 메모리를 사용하여 해결하였다.
이후에 우선순위 큐(Priority Queue)로 정렬하여 구현하는 것이 훨씬 빠르다는 설명을 듣고 직접 구현해보고자 하였다.
우선, java에서 재공하는 PriorityQueue 클래스를 알아보고자 하였다.
- 기본적인 메소드
PriorityQueue pQ = new PriorityQueue<>(Comparator);
// Comparator는 reverseOrder()나 Integer.compare()과 같은 람다식으로 사용 가능하다.
add() : 우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
offer() : 우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 null 반환
remove() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
isEmpty() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
clear() : 우선순위 큐를 초기화
size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환
peek() : 첫번째 원소를 삭제하지 않고 가져옴.
비교할 대상은 ListNode의 val 변수이기 때문에 람다식을 사용하여 구현하였다.
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length < 1) return null;
// val을 기준으로 비교할 우선순위 큐 생성
PriorityQueue<ListNode> pq = new PriorityQueue<>(
(a,b) -> Integer.compare(a.val, b.val)
);
// 첫 node들을 우선순위 큐에 넣기
for(ListNode node : lists){
if(node != null) pq.offer(node);
}
ListNode dump = new ListNode(-1);
ListNode current = dump;
// dump에 우선순위 큐의 값을 삽입 + 우선순위 큐에 다음 노드를 추가
while(!pq.isEmpty()){
// 첫번째 노드(제일 작은 값) 선택 후 제거
ListNode node = pq.poll();
// 결과 노드에 추가 및 다음 노드로 이동
current.next = node;
current = current.next;
// 다음 노드가 있으면 우선순위 큐에 추가
if(node.next != null) pq.offer(node.next);
}
return dump.next;
}
} 결과적으로 4ms에 44.62mb를 사용하면서 비슷한 메모리 용량으로 훨씬 빠르게 계산한 것을 확인했다.
우선순위 큐의 경우 O(Nlogn)의 시간복잡도를 가지므로 그냥 순회했던 이전 방법보다 훨씬 개선된 알고리즘이 구현 가능했다.
이후에 프로그래머스에서 관련 문제를 풀어보았다.
더 맵게
이 문제는 음식의 스코빌지수를 담은 배열을 가지고 모든 음식을 K 이상의 스코빌 지수로 만드는 문제이다.
모든 음식을 K 이상으로 만들 수 없는 경우에는 -1을 리턴하도록 예외처리해야 한다.
해결한 코드는 다음과 같다.
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Long> pq = new PriorityQueue<>();
// 우선순위 큐에 넣어서 기본적으로 정렬
for(int sov : scoville){
pq.offer(new Long(sov));
}
while(pq.peek() < K){
// 가장 작은 값 가져오기
long smallest = pq.poll();
// 큐가 비어있으면 예외처리
if(pq.isEmpty()) return -1;
// 섞은 스코빌 = 가장 작은 스코빌 + 두번째 스코빌 * 2
pq.offer(smallest + pq.poll() * 2);
answer++;
}
return answer;
}
}우선순위 큐를 사용하는 문제는 대체로 안에 있는 값을 추가, 삭제, 변환하여 계속해서 정렬할 때 유용한 알고리즘인 것 같다. 이후에도 잘 사용해봤으면 좋겠다.
