[JAVA] PriorityQueue

오늘내일·2023년 10월 5일
0

알고리즘 문제를 풀 때 잘 안 풀리는 부분이 PriorityQueue 유형이다.
그래서 기본적으로 PriorityQueue 사용하는 방법에 대해서 정리하려고 한다.

PriorityQueue 개념

우선순위큐는 일반적인 큐 구조와 달리 지정한 우선순위에 따라 데이터를 꺼내는 자료구조이다. 보통 최소힙 또는 최대힙 구조로 구성되어진다.

PriorityQueue 사용 예제

  1. 기본 Integer 추가

PriorityQueue를 그냥 선언하고 integer를 넣으면 기본적으로 최소값부터 꺼낼 수 있다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
        
pq.offer(3);
pq.offer(2);
pq.offer(1);
System.out.println(pq.poll());  //출력결과 1
System.out.println(pq.poll());  //출력결과 2
System.out.println(pq.poll());  //출력결과 3

최대값부터 꺼내려면 아래와 같이 선언부에 Collections.reverseOrder()를 추가하면 된다.

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

pq.offer(1);
pq.offer(2);
pq.offer(3);
System.out.println(pq.poll());  //출력결과 3
System.out.println(pq.poll());  //출력결과 2
System.out.println(pq.poll());  //출력결과 1
  1. 클래스 추가 by Comparable

PriorityQueue에 특정 클래스를 추가할 경우에는 클래스를 선언할 때 Comparable 인터페이스를 적용해야 한다. 아래 예제는 Member클래스의 나이 기준으로 PriorityQueue 자료구조를 이용하는 것이다. 인터페이스를 적용할 때 최소힙 구조로 자료를 꺼내고 싶으면 오버라이드 한 곳에 아래와 같이 this.age - o.age;를 리턴한다.

class Member implements Comparable<Member>{
    String name;
    int age;
    int size;
    Member(int age, int size){
        this.age = age;
        this.size = size;
    }

    @Override
    public int compareTo(Member o) {
        return this.age - o.age;
    }
}

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Member> pq = new PriorityQueue<>();
        pq.offer(new Member(20, 100));
        pq.offer(new Member(10, 105));
        pq.offer(new Member(30, 110));

        while(!pq.isEmpty()){
            Member member = pq.poll();
            System.out.printf("age : %d, size : %d\n",member.age, member.size);

        }
    }
}

//출력결과
//age : 10, size : 105
//age : 20, size : 100
//age : 30, size : 110

최대힙 구조로 하고 싶을 경우 클래스에 오버라이드한 곳에 this.age - o.age를 o.age - this.age로 바꿔주면 된다.

기본적으로 리턴값이 양수인 경우에는 두 객체의 자리를 바꾸고, 음수 또는 0이면 객체의 자리가 그대로 유지된다.
따라서 오름차순으로 하고 싶을 때는 this.age - o.age를 리턴하면, this.age > o.age일 때는 양수를 리턴하여 this.age와 o.age의 자리를 바꿔준고, this.age < o.age일 때는 음수를 리턴하여 자리를 그대로 유지하기 때문에 오름차순 정렬이 된다.

  1. int[] 추가 by Comparator

PriorityQueue에 배열을 넣고 싶을 때는 아래와 같이 Comparator를 이용하여 PriorityQueue를 사용할 수 있다. 아래는 compare함수에 o1[0]-o2[0]를 리턴시켜서 이용해서 0번 인덱스 값끼리 비교하였다.

	PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int[] a = {1, 3, 2};
        int[] b = {2, 3, 1};

        pq.offer(b);
        pq.offer(a);

        while(!pq.isEmpty()){
            int[] result = pq.poll();
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }

이를 응용해서 코테문제에서 사용할 수 있는 스킬을 살펴보자.

public static void main(String[] args) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = 0;
                for (int i = 0; i < Math.min(o1.length, o2.length); i++) {
                    if (o1[i] == o2[i]) {
                        if (i == Math.min(o1.length, o2.length) - 1) {
                            result = o1.length - o2.length;
                            break;
                        }
                    } else {
                        result = o1[i] - o2[i];
                        break;
                    }
                }
                return result;
            }
        });


        int[] c = {1};
        int[] b = {1, 2};
        int[] a = {1, 2, 3};
        int[] d = {1, 2, 4};

        pq.offer(a);
        pq.offer(b);
        pq.offer(c);
        pq.offer(d);

        while(!pq.isEmpty()){
            int[] result = pq.poll();
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
    }
//출력결과
1 
1 2 
1 2 3 
1 2 4

위의 예제를 설명해보면 배열의 0번째 인덱스 값부터 비교하는데 같은 인덱스의 값들에 따라 오름차순으로, 인덱스 값들이 같을 경우 배열의 길이가 더 긴 것을 뒤쪽으로 보낸 것이다.

profile
다시 시작합니다.

0개의 댓글