java priority queue 예제 : 비교자만 잘 작성해 봅시다.

 java에서 어떻게 Priority Queue를 쓸까요? 예제로 간단하게 알아보도록 하겠습니다.

 

---

 먼저, 기본적으로 Comparable이 구현이 되어 있는 경우에는, 따로 compareTo를 정의하지 않아도, 알아서 우선순위가 높은 것 부터 빠져나옴을 알 수 있어요. 예를 들자면 String 클래스의 경우에는 다음과 같이 선언이 되어 있습니다.

 

 

 여기서 중요한 것은 Comparable<String>입니다. 비교 가능하다는 것입니다.

 

 

 그러면 내부에 compareTo가 정의가 되어 있을 겁니다. 보니까 정의가 되어 있네요.

 

 

 

 예제 프로그램 1을 봅시다. 보통 pq를 구현할 때, 이런 식으로 많이 구현합니다. pq가 비었는지 확인하기 위해서, isEmpty를 호출합니다. 그리고, 맨 위에 있는 원소를 꺼내기 위해서 poll 메서드를 호출합니다.

 

 

 메서드 설명을 보면, queue의 맨 위에 있는 아이템을 리턴하면서, remove를 한다고 되어 있습니다. 만약에 retrieves만 하려면, 어떻게 해야 할까요?

 

 

 peek이나 element 등으로 top에 있는 원소를 보기만 하면 됩니다. ps에서 많이 써먹을 법 하니 peek과 구분해서 알아두시면 좋습니다. 7번째 줄에서 그러한 일을 수행합니다. 그리고 8번째 줄에서 큐의 맨 앞에 (top에 있는) 있는 것을 제거하기 위해서 poll 메서드를 호출하였습니다.

 

 

 peek에 대한 설명을 보면, 위와 같아요. retrives를 하나, 제거는 하지 않는다 되어 있어요.

 

 

 두 프로그램 다 실행 결과는 위와 같습니다. 여기서, 추가 요구 사항이 들어 왔습니다. pq에는 소문자로만 이루어진 문자열이 들어갈 건데요. 사전 순으로 뒤에 있는 것 부터 꺼내지게 만들고 싶습니다.

 

 

---

 그런데, String은 이미 comparable 하단 말입니다. 어떻게 해야 할까요? 이 때, Comparator를 쓰시면 됩니다.

 

 

 4번째 줄부터 9번째 줄까지를 보면, 새로운 Comparator를 넣었다는 것을 볼 수 있어요. 이 안에 compare가 있는데요. 이 메소드는 두 개의 객체를 비교하게끔 되어 있습니다. o1과 o2를 비교하는데요. 7번째 줄을 보니까, o1과 o2를 compareTo한 결과에 - 부호를 붙였습니다.

 

 이것은, 기존의 정렬 순서를 뒤집겠다는 이야기입니다. o1이 o2가 사전순으로 앞서면, o1.compareTo(o2)는 음수가 리턴이 될 건데요. 여기에 -를 붙이면, -o1.compareTo(o2)는 양수가 됩니다. 따라서, o1이 o2보다 사전순으로 뒤에 있다면, Comparator의 결과가 음수가 리턴이 됩니다. 뭔가 설명이 어려워 보이는데요. 어떻게 결과가 나오나 봅시다.

 

 

 bc, bc, a, a 순으로 나옴을 알 수 있습니다. 분명히 String은 자기 나름의 기준이 있었습니다. 이게 어떻게 바뀐 걸까요?

 

 

 이는 중간에 shifUp을 보면 알 수 있습니다. 644번째 줄에 comparator가 null이 아니면, 그대로 Comparator를 이용해서 shitUp을 합니다. 그렇지 않으면, Comparable을 이용해서 합니다. 그렇기 때문에 Comparator를 넣으면 그것을 기준으로 up 연산이나 down 연산을 하게 됩니다.

 

 

 해당 부분은 Lambda로 간략화 시킬 수 있습니다.

 

---

 이제, 커스텀 클래스를 생각해 보겠습니다. Dog 객체에는 이름과 나이가 있습니다. 그리고 저는 pq에서, 이름이 사전순으로 앞에 있으면 위에, 이름이 사전순으로 같다면 나이가 작으면 위에 있게 하고 싶습니다. 어떻게 하면 좋을까요?

 

 

 Comparable<Dog>를 implements를 하면 되는데요. this와 o를 비교한다고 생각하시면 편합니다. this와 o를 비교했을 때, this가 작으면 음수가, 같으면 0이, this가 더 크면 양수가 리턴되게 하면 되는데요. 먼저, this.name.compareTo(o.getName())의 리턴값을 가지고 비교합니다. 이를 제 1 비교순위라 칭하겠습니다.

 

 this의 name이 o의 name보다 작을 때 음수가 리턴되게 하려면, 24번째 줄처럼 작성해 주면 됩니다. 만약에 같다면, age를 가지고 비교를 하는데요. 마찬가지 논리로 생각해 보면, this의 나이와 o의 나이를 비교하는 것이니, this.age - o.getAge()를 리턴해 주게 하면 됩니다. 제 2 비교순위라고 생각하면 됩니다.

 

 

 Main 클래스는 위와 같습니다. 바뀐 것은 없습니다. 단지, Dog 클래스에 Comparable<Dog>를 implements 했다는 것이 중요합니다. 실행 결과는 아래와 같습니다.

 

 

 이름 사전순으로 먼저 빠지고, 이름이 같다면, 나이 오름차순으로 빠짐을 알 수 있습니다. 여담으로, hashCode나 equals도 왠만하면 오버라이딩을 해 주는 것이 좋습니다.