알고리즘 문제를 풀 때 잘 안 풀리는 부분이 PriorityQueue 유형이다.
그래서 기본적으로 PriorityQueue 사용하는 방법에 대해서 정리하려고 한다.
PriorityQueue 개념
우선순위큐는 일반적인 큐 구조와 달리 지정한 우선순위에 따라 데이터를 꺼내는 자료구조이다. 보통 최소힙 또는 최대힙 구조로 구성되어진다.
PriorityQueue 사용 예제
- 기본 Integer 추가
PriorityQueue를 그냥 선언하고 integer를 넣으면 기본적으로 최소값부터 꺼낼 수 있다.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(2);
pq.offer(1);
System.out.println(pq.poll()); //출력결과 1
System.out.println(pq.poll()); //출력결과 2
System.out.println(pq.poll()); //출력결과 3최대값부터 꺼내려면 아래와 같이 선언부에 Collections.reverseOrder()를 추가하면 된다.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);
pq.offer(2);
pq.offer(3);
System.out.println(pq.poll()); //출력결과 3
System.out.println(pq.poll()); //출력결과 2
System.out.println(pq.poll()); //출력결과 1- 클래스 추가 by Comparable
PriorityQueue에 특정 클래스를 추가할 경우에는 클래스를 선언할 때 Comparable 인터페이스를 적용해야 한다. 아래 예제는 Member클래스의 나이 기준으로 PriorityQueue 자료구조를 이용하는 것이다. 인터페이스를 적용할 때 최소힙 구조로 자료를 꺼내고 싶으면 오버라이드 한 곳에 아래와 같이 this.age - o.age;를 리턴한다.
class Member implements Comparable<Member>{
String name;
int age;
int size;
Member(int age, int size){
this.age = age;
this.size = size;
}
@Override
public int compareTo(Member o) {
return this.age - o.age;
}
}
public class Test {
public static void main(String[] args) {
PriorityQueue<Member> pq = new PriorityQueue<>();
pq.offer(new Member(20, 100));
pq.offer(new Member(10, 105));
pq.offer(new Member(30, 110));
while(!pq.isEmpty()){
Member member = pq.poll();
System.out.printf("age : %d, size : %d\n",member.age, member.size);
}
}
}
//출력결과
//age : 10, size : 105
//age : 20, size : 100
//age : 30, size : 110최대힙 구조로 하고 싶을 경우 클래스에 오버라이드한 곳에 this.age - o.age를 o.age - this.age로 바꿔주면 된다.
기본적으로 리턴값이 양수인 경우에는 두 객체의 자리를 바꾸고, 음수 또는 0이면 객체의 자리가 그대로 유지된다.
따라서 오름차순으로 하고 싶을 때는 this.age - o.age를 리턴하면, this.age > o.age일 때는 양수를 리턴하여 this.age와 o.age의 자리를 바꿔준고, this.age < o.age일 때는 음수를 리턴하여 자리를 그대로 유지하기 때문에 오름차순 정렬이 된다.
- int[] 추가 by Comparator
PriorityQueue에 배열을 넣고 싶을 때는 아래와 같이 Comparator를 이용하여 PriorityQueue를 사용할 수 있다. 아래는 compare함수에 o1[0]-o2[0]를 리턴시켜서 이용해서 0번 인덱스 값끼리 비교하였다.
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int[] a = {1, 3, 2};
int[] b = {2, 3, 1};
pq.offer(b);
pq.offer(a);
while(!pq.isEmpty()){
int[] result = pq.poll();
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]+" ");
}
System.out.println();
}이를 응용해서 코테문제에서 사용할 수 있는 스킬을 살펴보자.
public static void main(String[] args) {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int result = 0;
for (int i = 0; i < Math.min(o1.length, o2.length); i++) {
if (o1[i] == o2[i]) {
if (i == Math.min(o1.length, o2.length) - 1) {
result = o1.length - o2.length;
break;
}
} else {
result = o1[i] - o2[i];
break;
}
}
return result;
}
});
int[] c = {1};
int[] b = {1, 2};
int[] a = {1, 2, 3};
int[] d = {1, 2, 4};
pq.offer(a);
pq.offer(b);
pq.offer(c);
pq.offer(d);
while(!pq.isEmpty()){
int[] result = pq.poll();
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]+" ");
}
System.out.println();
}
}
//출력결과
1
1 2
1 2 3
1 2 4위의 예제를 설명해보면 배열의 0번째 인덱스 값부터 비교하는데 같은 인덱스의 값들에 따라 오름차순으로, 인덱스 값들이 같을 경우 배열의 길이가 더 긴 것을 뒤쪽으로 보낸 것이다.
