[BOJ] 27단계 우선순위 큐

우선순위 큐(Priority Queue): 가장 작은/큰 원소를 뽑는 자료구조

• 최대 힙: 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙
• 최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙

자바의 PriorityQueue<? extends Comparable>

내부 요소는 힙(이진 트리)으로 구성되어 시간 복잡도 O(nlogn)

defalut: 최소 힙최대 힙으로 바꾸고 싶으면 Collection.reverseOrder() 사용

• poll(): 첫번째 값 반환하고 제거, 비어 있다면 null
• remove(): 첫번째 값 반환하고 제거, 비어있다면 예외 발생
• peek(): 첫번째 값 반환, 비어 있다면 null
• element(): 번째 값 반환, 비어있다면 예외 발생

 

1

11279

최대 힙

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            int input = Integer.parseInt(reader.readLine());
            if(input == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            } else {
                pq.add(input);
            }
        }
        System.out.print(sb);
    }

}

*PriorityQueue 생성자에 Collection.reverseOrder() -> 최대 힙

 

2

1927

최소 힙

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            int input = Integer.parseInt(reader.readLine());
            if(input == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            } else {
                pq.add(input);
            }
        }
        System.out.print(sb);
    }
}

 

3

11286

절댓값 힙

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(Math.abs(o1) == Math.abs(o2)) {
                    return o1 - o2;
                }
                return Math.abs(o1) - Math.abs(o2);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            int input = Integer.parseInt(reader.readLine());
            if(input == 0) {
                if(pq.isEmpty()) {
                    sb.append(0).append("\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            } else {
                pq.add(input);
            }
        }
        System.out.print(sb);
    }

}

*Comparator 재정의