[Java] 우선순위 큐(Priority Queue)와 정렬(Order)

들어가며

코딩테스트에 있어서 파이썬 언어를 주로 활용하다가 자바로 언어를 제한하는 회사가 많아진 것 같은 느낌이 들었다.. 내 사랑 파이썬... 그도 그럴 것이 자바로 프로그래밍을 하면서 자바 언어를 활용 못한다는 것도 웃기는 일이다. 그래서 자바 언어로 코딩테스트 준비를 하던 중에 가장 헷갈렸던 부분이 바로 "우선순위 큐" 부분이었다. 그래서 우선순위 큐 정렬 부분을 확실하게 정리하려고 한다.

단일 조건

자바와 파이썬에서 기본적으로 우선순위 큐를 선언하면 minHeap으로 기본으로 설정된다. 즉, 단일 숫자 조건이라면 가장 낮은 숫자가 가장 높은 우선순위를 가진다는 의미이다. 코드를 살펴보자.

import java.math.*;
import java.util.*;

class Main {

  private static final PriorityQueue<Integer> pq = new PriorityQueue<>();

  public static void main(String[] args) throws IOException {

    for (int i = 1; i <= 5; i++) {
      pq.offer(i);
    }

    while (!pq.isEmpty()) {
      System.out.print(pq.poll() + " "); // 1 2 3 4 5
    }
  }
}

 

여기서 만약에 maxHeap으로 구현하고자 한다면, 다음과 같이 Collections.reverseOrder()라는 정렬 기준 메서드를 PriorityQueue 생성자 인자 조건으로 추가해 주면 된다. 즉, Collections.reverseOrder() 메서드가 Comparator 객체를 반환하면서 maxHeap 정렬 기준으로 활용되는 것이다. 

import java.math.*;
import java.util.*;

class Main {

  private static final PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

  public static void main(String[] args) throws IOException {

    for (int i = 1; i <= 5; i++) {
      pq.offer(i);
    }

    while (!pq.isEmpty()) {
      System.out.print(pq.poll() + " "); // 5 4 3 2 1
    }
  }
}

 

익명 클래스 또는 람다식을 활용해서도 위 내용을 구현할 수 있다.

방법 1. 오름차순인 경우 

import java.io.*;
import java.util.*;

class Main {

  private static PriorityQueue<Integer> pq1;
  private static PriorityQueue<Integer> pq2;

  public static void main(String[] args) throws IOException {

    // 익명 클래스 방식으로 Comparator 구현
    pq1 = new PriorityQueue<>(new Comparator<Integer>() {
      @Override
      public int compare(Integer a, Integer b) {
        return a - b; // 오름차순
      }
    });

    // 람다식 방식으로 Comparator 구현
    pq2 = new PriorityQueue<>((a, b) -> a - b); // 오름차순

    for (int i = 1; i <= 5; i++) {
      pq2.offer(i);
    }

    while (!pq2.isEmpty()) {
      System.out.print(pq2.poll() + " ");
    }
  }
}

방법 2. 내림차순인 경우 

import java.io.*;
import java.util.*;

class Main {

  private static PriorityQueue<Integer> pq1;
  private static PriorityQueue<Integer> pq2;

  public static void main(String[] args) throws IOException {

    // 익명 클래스 방식으로 Comparator 구현
    pq1 = new PriorityQueue<>(new Comparator<Integer>() {
      @Override
      public int compare(Integer a, Integer b) {
        return b - a; // 내림차순
      }
    });

    // 람다식 방식으로 Comparator 구현
    pq2 = new PriorityQueue<>((a, b) -> b - a); // 내림차순

    for (int i = 1; i <= 5; i++) {
      pq2.offer(i);
    }

    while (!pq2.isEmpty()) {
      System.out.print(pq2.poll() + " ");
    }
  }
}

 

이렇게 하나의 Integer 타입의 숫자인 경우에는 헷갈리지도 않고, 그냥 선언만 하면 되니까 활용하기 편했다. 그런데, 나는 다중 조건이 들어왔을 때, 첫번째 숫자에 대해서는 오름차순, 두 번째 숫자에 대해서는 내림차순과 같이 다양한 정렬 조건을 필요로 하는 상황에서 막상 코드를 짜려고 할 때 어려움을 느꼈다. 

다중 조건 

다중 정렬을 하기 위해서는 크게 Comparable 인터페이스를 활용하는 방법과 Comparator 인터페이스를 활용하는 방법이 있다.

방법 1. Comparable 인터페이스를 활용하는 다중 정렬 방법

조건. Person 객체에서 키가 큰 순서대로, 키가 같다면 나이가 작은 순서대로 정렬

import java.io.*;
import java.util.*;

class Main {

  static class Person implements Comparable<Person> {

    int tall;
    int age;

    Person(int tall, int age) {
      this.tall = tall;
      this.age = age;
    }

    @Override
    public int compareTo(Person other) {
      // 키가 같다면 -> 나이가 많은 순서
      if (this.tall == other.tall) {
        return Integer.compare(this.age, other.age);
      }
      // 키가 다르다면 -> 키가 큰 순서
      return Integer.compare(other.tall, this.tall);
    }
  }

  private static PriorityQueue<Person> pq = new PriorityQueue<>();

  public static void main(String[] args) throws IOException {

    Person p1 = new Person(173, 25);
    Person p2 = new Person(180, 15);
    Person p3 = new Person(170, 30);
    Person p4 = new Person(173, 30);

    pq.offer(p1);
    pq.offer(p2);
    pq.offer(p3);
    pq.offer(p4);

    while (!pq.isEmpty()) {
      Person p = pq.poll();
      System.out.println("키: " + p.tall + ", 나이: " + p.age);
    }
  }
}

 

위 결과와 같이 먼저 설정한 정렬 조건대로 값들을 잘 반환하는 것을 확인할 수 있었다.

방법 2. Comparator 인터페이스를 활용하는 다중 정렬 방법 

import java.io.*;
import java.util.*;

class Main {

  static class Person {

    int tall;
    int age;

    Person(int tall, int age) {
      this.tall = tall;
      this.age = age;
    }
  }

  private static final Comparator<Person> personComparator = (p1, p2) -> {
    // 키가 같다면 -> 나이가 작은 순서
    if (p1.tall == p2.tall) {
      return Integer.compare(p1.age, p2.age);
    }
    // 키가 다르다면 -> 키가 큰 순서
    return Integer.compare(p2.tall, p1.tall);
  };

  private static PriorityQueue<Person> pq = new PriorityQueue<>(personComparator);

  public static void main(String[] args) throws IOException {

    Person p1 = new Person(173, 25);
    Person p2 = new Person(180, 15);
    Person p3 = new Person(170, 30);
    Person p4 = new Person(173, 30);

    pq.offer(p1);
    pq.offer(p2);
    pq.offer(p3);
    pq.offer(p4);

    while (!pq.isEmpty()) {
      Person p = pq.poll();
      System.out.println("키: " + p.tall + ", 나이: " + p.age);
    }
  }
}

마찬가지로 같은 결과가 나오는 것을 확인할 수 있었다. 

 

여기서 오름차순, 내림차순을 결정할 때, p1 - p2와 p2 - p1 둘 중 어느 것으로 선택해야할 지 매우 헷갈린다는 것이다. 나는 헷갈리지 않기 위해서 다음과 같이 생각하기로 마음먹었다.

 

현재 값 또는 객체를 기준으로 오름차순으로 정렬하고 싶다면, 현재 객체를 가장 앞에 두고 싶다!

-> Integer.compare(p1, p2) 또는 Integer.compare(this, other)

현재 값 또는 객체를 기준으로 내림차순으로 정렬하고 싶다면, 현재 객체를 가장 뒤에 두고 싶다!

-> Integer.compare(p2, p1) 또는 Integer.compare(other, this)

 

억지 같지만,,, 그냥 오름차순인 경우에는 먼저 선언한 값이 먼저 나오게 하고 싶다는 생각으로 "this - other"으로 생각하기로 했다... 그러면 Comparable 인터페이스를 사용하는 경우와 Comparator 인터페이스를 사용하는 경우에는 어떤 차이점이 있을까?

정리

직접 두가지 방법을 코딩하면서 느낀 점은 Comparable 인터페이스를 활용하는 경우가 조금 더 편했다. 그냥 정렬 대상인 클래스를 구현하면서 아예 정렬 기준을 정해버렸기 때문에, 실제 로직을 구현할 때에는 문제 풀이 로직만 구현하면 됐기 때문이다. Comparator 인터페이스 방법은 정렬 기준을 아예 외부로 구현하기 때문에 정렬 기준을 다양하게 갈아 끼우는 상황에서 편할 것 같다는 생각이 들었다. 단일 조건에서의 정렬을 결정하는 방법과 다중 조건에서 정렬을 결정하는 방법을 다시는 까먹지 않고, 헷갈리지 않도록 하자!!