[자료구조] 우선순위 큐 (priority queue) - 백준 1715번

배경

백준 1715번: 카드 정렬하기(그리디 알고리즘) 문제를 ArrayList로 풀다가 시간 초과가 뜨길래 문제를 해결하던 중 우선순위 큐를 적용해야만 한다는 걸 알게되었다.

 

처음에는 List 클래스의 sort() 메서드 사용 시 오름차순 정렬을 했기 때문에 연산이 완료된 값을 삭제할 때 배열이 전체 이동되어 시간이 많이 소요되는 거라고 생각했다. 그래서 내림차순 정렬로 바꾸고, ArrayList의 끝부분에서 삽입 삭제 시에 배열의 전체 복사나 이동이 없게끔 코드를 변경했는데, 여전히 시간초과가 뜨길래 결국 다른 사람들의 풀이를 검색할 수 밖에 없었다.

 

//ArrayList를 사용한 예시 - 시간초과
while(list.size() > 1) {
				
    list.sort(Comparator.reverseOrder());
    sum = list.get(list.size()-1) + list.get(list.size()-2);
    total += sum;

    list.set(list.size() - 2, sum);
    list.remove(list.size() - 1);
}

 

알고보니 막상 시간을 많이 잡아먹는 구간은 정렬이었는데, ArrayList 사용 시 최소값을 찾기 위해서는 값을 삽입해줄 때마다 정렬을 수행할 수밖에 없고, 이런 식으로 접근하면 O(N^2 logN)의 시간복잡도가 나온다고 하니 애초에 자료구조를 바꿔서 해결해야 하는 문제였던 것이다. 우선순위 큐에 대해 간단히 알아보자.

우선순위 큐

우선순위 큐(priority queue)는 저장된 데이터를 저장된 순서에 관계없이 우선순위가 높은 순서대로 꺼낼 수 있게끔 만들어진 큐(queue)의 일종이며, 자료구조 중 힙(heap)의 형태로 저장된다. 힙은 완전이진트리(complete binary tree)의 형태를 지녔는데 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 장점을 가지고 있다. 

 

우선순위 큐의 구현은 배열(array)이나 연결리스트(linked list)로도 가능하나, 이 둘의 경우 데이터 삽입 시 삽입 위치를 찾기위한 탐색 과정에서 전체를 탐색해야하기 때문에 복잡도가 최대 O(N)이 된다. 힙으로 구현할 경우에는 부모와 자식노드간의 비교만 이루어지면 되어 삽입 시 복잡도는 최대 O(log2N)이 되어 배열이나 연결리스트를 사용할 때보다 유리하다고 할 수 있다. 그래서 보통 우선순위 큐는 힙으로 구현된다.

PriorityQueue (자바 컬렉션 클래스)

자바의 컬렉션 중 Queue 인터페이스의 구현 클래스 중 하나로, 우선순위 큐를 사용할 수 있도록 정의해놓은 클래스이다. 숫자를 저장할 경우에는 숫자가 작을 수록 높은 우선순위를 부여하여 저장되며, 컴파일러가 알아서 primitive 자료 -> wrapper 클래스(예: int -> Integer) 로의 오토박싱을 수행해준다는 특징이 있다. 숫자가 아닌 객체를 저장할 때에는 객체끼리의 우선순위 비교 방법을 별도로 정의해주어야 한다.

 

//PriorityQueue를 사용한 예시 - 통과
Queue<Integer> pq = new PriorityQueue<Integer>();
			
for(int i=0; i<n; i++) {
    pq.offer(Integer.parseInt(br.readLine()));
}

int sum = 0;	//부분합
int total = 0;	//출력될 총합

while(pq.size() > 1) {

    sum = pq.poll() + pq.poll();
    total += sum;

    pq.offer(sum);
}

Note

- 우선순위 큐를 사용하니 문제는 금방 해결되었다.

- 앞으로는 자료구조를 적재적소에 활용할 수 있도록 머리속에 확실히 정리해놓아야겠다.