우선순위 큐 (Priority Queue), 힙 (Heap)

우선순위 큐는 넣을 때는 자유롭게, 꺼낼 때는 항상 우선순위가 가장 높은 것부터 나오는 자료구조입니다.

코드로 보면 아래와 같습니다.

// 예시: 기본적으로 작은 값이 우선)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);

System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 5

// 예시: 내림차순으로 하고 싶을 때
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq2.add(5);
pq2.add(1);
pq2.add(3);

System.out.println(pq2.poll()); // 5
System.out.println(pq2.poll()); // 3
System.out.println(pq2.poll()); // 1

 

우선순위 큐는 내부적으로 힙(heap)이라는 자료구조로 되어있습니다.

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조입니다.

힙의 예시

 

형제 노드간의 대소 관계는 정의되어 있지 않으며 부모와 자식의 대소 관계만 정의된 반정렬 상태가 특징입니다.

힙의 종류는 아래와 같이 2가지가 있습니다.

• 최대 힙: 부모 노드의 값이 자식 노드보다 항상 크거나 같다. → 루트 노드에 가장 큰 값이 위치
• 최소 힙: 부모 노드의 값이 자식 노드보다 항상 작거나 같다. → 루트 노드에 가장 작은 값이 위치

시간 복잡도는 아래와 같습니다.

• 최솟값/최댓값 확인: 루트 노트만 확인하면 되므로 O(1)
• 데이터 삽입: 가장 끝에 노드를 추가한 뒤 부모와 비교하면서 위로 올라가면 되므로 트리 높이만큼만 이동하면 된다. O(log N)
• 데이터 삭제: 루트 노드를 꺼낸 후 가장 마지막 노드를 루트 노드로 옮기고 자식과 비교하면서 아래로 내려가면 되므로 O(log N)

 

문제 풀어보기

백준 11286

 

풀이

과정을 정리해보면 아래와 같다.

1. 연산의 개수(N)을 입력받음
2. N번의 반복문을 돌면서 값(x)을 입력받는데 입력받은 값에 따라서 아래와 같은 동작을 한다.
   1. x가 0이 아니라면 배열에 x를 추가
   2. x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 제거, 절대값이 가장 작은 수가 여러개라면 원래 수를 비교해서 가장 작은 값을 출력 및 제거

최솟값을 찾아야 하므로 그냥 배열로 하는 것보다 우선순위 큐를 이용하는 것이 효율적이라 판단됩니다.

그래서 코드를 구현하면 아래와 같습니다.

 

코드 구현

    private static void 절대값_힙() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> {
            int absA = Math.abs(a);
            int absB = Math.abs(b);
            if(absA == absB) return a-b;
            return absA - absB;
        });

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());

            if(num == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            } else {
                pq.add(num);
            }
        }

        System.out.println(sb);
    }