[알고리즘] 우선순위큐(힙)는 왜, 언제 사용해야 할까

언제, 왜 우선순위 큐를 사용해야 하는가?

문제를 풀 때, 원소를 삽입 또는 삭제 후 매번 정렬을 해야하는 문제가 있다.

이럴 때에는 Collections.sort 와 같은 퀵정렬을 이용하게 되면 시간복잡도가 nlogn 이다. 

이때 원소의 개수가 1e6 이상인 경우에 퀵정렬 시간복잡도는 1e8 을 넘어갈 수 있게 된다. 

따라서 이때에는 우선순위 큐를 활용하여야 원소를 삽입 또는 삭제할 때 마다 nlogn 이 아닌, logn 의 시간복잡도로 정렬할 수 있게된다.

적용

가장 대표적인 문제는 프로그래머스의 '더 맵게' 문제이다. 

https://programmers.co.kr/learn/courses/30/lessons/42626?language=java

풀이1

위 코드는 내장 sort 를 이용하여 원소를 삭제,삽입 후 매번 nlogn 의 시간복잡도로 정렬을 하는 방식이다. 이 경우에는 정확도 테스트는 모두 통과했으나 효율성 테스트에서 모두 시간초과가 떴다. 

풀이 2

이렇게 우선순위 큐로 개선을 한 결과 효율성 테스트까지 모두 통과한 것을 알 수 있다. 

참고

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

위와같이 선언하면 최대힙(내림차순)을 구성할 수 있다.

pq.remove(Object o) // o 값 삭제