[자료구조] 우선순위큐에 비교로직 전달하기

 

JAVA에서 우선순위 기준이 복잡할 때,

정렬을 위해 주로 사용하는 자료구조가 우선순위큐(PriorityQueue)이다. 

 

우선순위큐가 내가 원하는 우선순위대로 정렬하려면,

비교로직을 우선순위큐에 전달해야 한다.

 

이번 포스팅은 우선순위큐에 비교로직을 전달하는 방법을 알아보겠다. 

 

예시 정렬기준 ( 여러 단어를 3가지 기준으로 정렬한다. )

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 

1) Comparable 인터페이스

 

우선순위큐는 객체를 기준으로 정렬하는데, 객체가 자체적인 정렬기준을 가지고 있으면 우선순위큐가 알아서 참조하여 정렬한다. 객체가 자체적인 정렬기준을 가지려면 Comparable 인터페이스를 구현해서 compareTo 메소드를 재정의 하면 된다. 

 

public class Test {
    public static void main(String[] args) throws IOException {
	// 중략 ...
        
        PriorityQueue<Word> pq = new PriorityQueue<>();
        
        // 중략 ...
    }

    public static class Word implements Comparable<Word>{
        String value; 
        int count;

        public Word(String value, int count){
            this.value = value;
            this.count = count;
        }

        @Override
        public int compareTo(Word word){
            if( this.count == word.count ){
                if(this.value.length() == word.value.length()){
                    return this.value.compareTo(word.value); // 3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. ( 오름차순 )
                }else{
                    return word.value.length() - this.value.length(); //2 . 해당 단어의 길이가 길수록 앞에 배치한다. ( 내림차순 )
                }
            }else{
                return word.count - this.count; // 1. 자주 나오는 단어일수록 앞에 배치한다( 내림차순 )
            }
        }
    }
}

 

 

 

compareTo 메소드는 a.compareTo(B b)로 이루어져 있다. compareTo를 소유한 a 객체와 compareTo의 파라미터로 들어온 b객체를 비교한다. 객체의 크고 작음은 멤버변수로 표현하면 된다. a객체는 this, b객체는 파라미터이다.

 

1. 자주 나오는 단어일수록 앞에 배치한다. ( 내림차순 )
2. 해당 단어의 길이가 길수록 앞에 배치한다. ( 내림차순 )
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. ( 오름차순 )

 

정렬기준이 오름차순이면 this 맴버변수 - 파라미터 멤버변수이고

정렬기준이 내림차순이면 파라미터 멤버변수 - this 멤버변수이다.

 

만약 문자열이라고 한다면

 

this 문자열.compareTo(파라미터 문자열) ( 오름차순 )이고

파라미터 문자열.compareTo(this 문자열) ( 내림차순 )이다.

 

 

2) Comparator 인터페이스

 

Comparator 인터페이스는 함수형 인터페이스이다.  함수형 인터페이스는 메소드가 하나 밖에 없는 인터페이스로, A에서 B로 로직을 전달할 때 사용되는 인터페이스이다. 전달하고 싶은 로직을 함수형 인터페이스의 메소드에 정의하면 된다.

 

Comparator는 비교로직을 전달하는 함수형 인터페이스로, PriorityQueue의 생성자 파라미터로 넘기면, PriorityQueue가 비교로직을 참고하여 정렬을 한다. 

 

public class Test {

    public static void main(String[] args) throws IOException {
    
    // Priority Queue 생성자로 Comparator 객체 전달
        PriorityQueue<Word> pq = new PriorityQueue<>(new WordComparator());
        
    }
    
    // Comparator 함수형 인터페이스 
    public static class WordComparator implements Comparator<Word>{

        @Override
        public int compare(Word w1, Word w2){
            if( w1.count == w2.count ){
                if(w1.value.length() == w2.value.length()){
                    return w1.value.compareTo(w2.value);
                }else{
                    return w2.value.length() - w1.value.length();
                }
            }else{
                return w2.count - w1.count;
            }
        }
    }

    public static class Word {
        String value;
        int count;

        public Word(String value, int count){
            this.value = value;
            this.count = count;
        }
    }



}

 

 

Comparable 인터페이스는 this와 파라미터로 내림차순, 오름차순을 구분했다. Comparator 인터페이스는 첫번째 파라미터, 두번째 파라미터로 내림차순 오름차순을 구분한다. 

 

1. 자주 나오는 단어일수록 앞에 배치한다. ( 내림차순 )
2. 해당 단어의 길이가 길수록 앞에 배치한다. ( 내림차순 )
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. ( 오름차순 )

 

정렬기준이 오름차순이면 첫번째 파라미터 맴버변수 - 두번째 파라미터 멤버변수이고

정렬기준이 내림차순이면 두번째 파라미터 멤버변수 - 첫번째 파라미터 멤버변수이다.

 

만약 문자열이라고 한다면

 

첫번째 파라미터 문자열.compareTo(두번째 파라미터 문자열) ( 오름차순 )이고

두번째 파라미터 문자열.compareTo(첫번째 파라미터 문자열) ( 내림차순 )이다.

 

 

3) Comparator 인터페이스 객체 람다표현식으로 전달하기 

 

Comparator 인터페이스는 함수형 인터페이스이니 굳이 클래스를 따로 생성하지 않아도 된다. PriorityQueue 생성자 파라미터로 넘길대 익명 클래스로 넘기거나 람다 표현식으로 넘기면 된다. 

 

public class Test {

    public static void main(String[] args) throws IOException {
    
  	// 람다 표현식으로 비교로직 넘기기
        PriorityQueue<Word> pq = new PriorityQueue<>( (w1,w2)->{
            if( w1.count == w2.count ){
                if(w1.value.length() == w2.value.length()){
                    return w1.value.compareTo(w2.value);
                }else{
                    return w2.value.length() - w1.value.length();
                }
            }else{
                return w2.count - w1.count;
            }
        });
    }

    public static class Word {
        String value;
        int count;

        public Word(String value, int count){
            this.value = value;
            this.count = count;
        }
    }

}