알고리즘 문제를 해결하다 보면 정렬시키거나 우선순위 큐를 사용할 때가 있다.

그런데 만약 다익스트라 알고리즘을 사용해야 해서 단순히 값 1개만 가지고 있는게 아니라, 우선순위 값과 우선순위에 해당하는 정보를 가지고 있는 경우에 어떻게 해야할까?

2가지 방법이 존재한다.

• Comparable
• Comparator

Comparable

Comparable은 Interface이다. 주로 단순한 Integer나 String보다 객체를 정렬하거나 비교할 때 사용한다.

Comparable을 implements하면 compareTo를 Override해야한다. compareTo는 return 값을 3가지로 분류한다.

• 양수
• 0
• 음수

실제로 자바에서 compareTo에 대해 살펴보면 다음과 같이 작성되어 있다.

설명을 읽어보면, return값은 다음과 같다.

• 이 객체가 특정 객체보다 작다면 음수
• 이 객체가 특정 객체와 같다면 0
• 이 객체가 특정 객체보다 크다면 양수

만약 예를 들어 다음과 같은 객체가 있다고 가정해보자.

class Node {
		int num;
		int priority;
		
		public Node(int num, int priority) {
				this.num = num;
				this.priority = priority;
		}
}

만약 List가 존재하고 이 때 priority가 큰 노드가 앞으로 오도록 정렬하고 싶은 상황이라고 해보자.

우선 Node를 Comaprable의 구현체로 설정한다.

class Node implements Comparable<Node> {
		int num;
		int priority;
		
		public Node(int num, int priority) {
				this.num = num;
				this.priority = priority;
		}
		@Override
		public int compareTo(Node o) {
				// compareTo 구현
		}
}

Comparable 뒤에 를 적어서 compareTo의 인자로 Node를 받을 수 있도록 했다.

이제 compareTo를 구현해보자. compareTo의 return 값을 다시 보면 다음과 같다.

• 이 객체가 특정 객체보다 작다면 음수
• 이 객체가 특정 객체와 같다면 0
• 이 객체가 특정 객체보다 크다면 양수

우리는 priority가 큰 노드가 앞으로 오길 원하는 상황이다. 그러므로 다음과 같이 작성한다.

@Override
public int compareTo(Node o) {
		return o.priority - this.priority;
}

나의 priority가 5이고 비교 대상의 priority가 3이라고 해보자. 그러면 음수값으로 return하게 된다. 즉 내가 더 작다는 뜻이다.

그런데 ‘우리는 priority가 큰 값이 앞 부분에 있도록 구현하는 것이 목표인데, 그러면 내가 더 크니까 양수값으로 return해야 되는게 아닐까?’ 하는 의문이 든다.

List 정렬 시 오름차순으로 정렬된다. 우리가 Comparable을 구현한 객체를 만들어서 compareTo를 작성했을 때 음수를 반환한다는 것은 compareTo 메소드를 실행한 객체가 더 앞에 간다는 뜻이다.

그래서 실제로 리스트를 생성하고 Node를 넣은 후 Collections.sort(list); 를 실행해보면 priority가 큰 값이 먼저 오는 것을 확인할 수 있다.

Comparator

Comparator를 이용하여 정렬시키는 방법은 Comparable과 유사하다.

우리가 List list가 있을 때, List의 sort 메소드를 실행시키려하면 Comparator를 인자로 넣어주어야 한다.

Comparator는 Comparable의 compareTo 메소드와 유사한 compare 메소드를 이용하여 비교한다. 설명은 다음과 같다.

o1과 o2 두 개를 인자로 받고 3가지 경우를 return 값으로 사용한다.

• o1이 o2보다 작다면 음수
• o1이 o2와 같다면 0
• o1이 o2보다 크다면 양수

compareTo는 하나의 객체를 중심으로 비교 대상이 들어왔을 때 비교하는 방식을 구현한 것인 반면에 , Comparator의 compare는 2개의 객체를 인자로 받고 인자로 받은 2개의 객체를 비교한다.

간단하게 말하자면 compareTo의 this가 o1이 되는 것이다.

실제로 다음과 같이 구현해보면 같은 결과를 반환한다.

list.sort(new Comparator<Node>() {
		@Override
		public int compare(Node o1, Node o2) {
				return o2.priority - o1.priority;
		}
});

요약

이전에 알고리즘 문제를 해결할 때, 어떻게 우선순위를 계산할지는 생각했는데 compareTo나 compare 메소드의 return값을 설정하는게 헷갈렸다.

간단히 생각하면, 내가 먼저 나와야하면 음수값을 return 한다.

여기서 말하는 ‘나’는 Comparable의 경우 this, Comparator의 경우 o1을 말한다.