Java의 객체 정렬과 객체 우선순위 큐

난 C++를 사랑하는데... 기업들은 C++를 사랑하지 않는다..ㅠㅠ 그래서 코딩테스트를 준비해야하기 때문에 요즘 자바로 C++로 풀었던 것들을 다시 풀고있다.

 

그러다가 개인적으로 자바에서 가장 불편한 부분이 바로 정렬과 우선순위큐 였는데 이번 기회에 한번에 정리하고 가겠다.

 

예제는 강의실 배정 문제이다. 이 문제는 아주 베이직하게 정렬과 우선순위큐를 활용해야하는 문제이기 때문에 가져왔다.

 

예제

3

1 3

3 4

2 3

 

-> 여기서 정렬했을 땐 

 

1 3

3 4

2 3

 

순으로 나와야하고 세개가 모두 우선순위큐에 있다면

 

3 4

1 3

2 3

 

순서로 나와야한다.

 

Comparator 와 Comparable 의 차이

잠시 영어시간을 가져보면 전자는 비교자, 후자는 비교할수있는? 이런 뜻이다. 그러니까 전자는 실제 sort 함수에서 new 비교자로 사용될 수 있고, 후자는 클래스에 임플리멘트 되어서 실제 오버라이딩을 통해 우선순위 큐를 정의할 수 있다.

 

난 이 문제를 풀 때 처음에 컴페어레이블을 구현하고 나니 우선순위큐는 해결했지만 정렬시 우선순위 큐의 조건으로 되어버렸다. 그래서 정렬할 때는 new Comparator로 정렬하는 것이 좋아보인다.

 

Array<class> 내부 : {
	3, 4
    1, 3
    2, 3
}

Array.sort(new Comparator<class>(){
	@Override
    public int compare(task o1, task o2){
    	 if (o1.start == o2.start) {
                    if (o1.end < o2.end) {
                        return -1;
                    } else {
                        return 1;
                    }
                } else {
                    if (o1.start < o2.start) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
    }
});

 

이렇게 정렬이 가능하고 이제 우선순위큐는?

 

 static class task implements Comparable<task>{
        int start, end;

        public task(int start , int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(task t){
            if(this.end == t.end){
                if(this.start < t.start){
                    return -1;
                }else{
                    return 1;
                }
            }else{
                if(this.end < t.end){
                    return -1;
                }else{
                    return 1;
                }
            }
        }
    }

 

클래스에 Compareble 을 임플리멘트 하고 compareTo 를 오버라이딩하고 특이한건 this와 한개의 파라미터를 받아 순서를 결정한다.