[코드트리 챌린지] 6주차 - 시간최적화(Priority Queue)

★ 핵심 : Priority Queue는 우선순위가 있는 큐!

1. Java의 Priority Queue

import java.util.PriorityQueue; 

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
    }
}

· Java에서의 PriorityQueue 는 기본적으로 최소 우선순위 큐

· 자주 사용되는 메서드

    1) add() - 우선순위 큐에 데이터 추가

    2) size() - 현재 우선순위 큐에 들어있는 데이터의 수 반환

    3) isEmpty() - 비어있으면 true, 아니라면 false

    4) peek() - 최솟값에 해당하는 데이터 반환

    5) poll() - 최솟값에 해당하는 데이터 반환 & 우선순위 큐에서 삭제

· 최대 우선순위 큐

    1) - 를 붙여 관리 ← 파이썬에서는 이렇게 함

    Ex) 우선순위 큐 원소 1, 2, 5가 있을 때 peek() 하면 1이 반환

           원소들을 넣을 때 -1, -2, -5로 넣고 peek() 하면 -5가 반환되고 - 붙여서 최종 반환하면 5, 최대값이 반환

    2) 자바에서는 또 다른 방법

class MaxPriorityQueueManager {
    private PriorityQueue<Integer> pq;

    public MaxPriorityQueueManager() {
        pq = new PriorityQueue<>(Collections.reverseOrder());
    }

//...

---

https://www.codetree.ai/cote/13/problems/process-numeric-command&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

· 핵심

1. 최대 우선순위 큐이다.

→ - 을 붙여서 최대 우선순위 큐 구현

---

· 코드(Java)

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

class PriorityQueueManager {
    private PriorityQueue<Integer> pq;

    public PriorityQueueManager() {
        pq = new PriorityQueue<>();
    }

    public void push(int n) {
        pq.add(-n);
    }

    public int pop() {
       if (pq.isEmpty()) {
            return -1;
        }
        return -pq.poll();
    }

    public int size() {
        return pq.size();
    }

    public int empty() {
        return pq.isEmpty() ? 1 : 0;
    }

    public int top() {
       if (pq.isEmpty()) {
            return -1;
        }
        return -pq.peek();
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        PriorityQueueManager pqManager = new PriorityQueueManager();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            if (cmd.equals("push")) {
                int num = Integer.parseInt(st.nextToken());
                pqManager.push(num);
            } 
            if (cmd.equals("pop")) {
                System.out.println(pqManager.pop());
            }
            if (cmd.equals("size")) {
                System.out.println(pqManager.size());
            }
            if (cmd.equals("empty")) {
                System.out.println(pqManager.empty());
            } 
            if (cmd.equals("top")) {
                System.out.println(pqManager.top());
            }
        }
    }
}

 

※ 실력진단

PS. DP를 공부해야하는데 공부 못해서 점수가 항상 같다. DP푼지가 오래되가지고 기억이 잘 안 나더라. 다음 주는 연습해야할 것 같다.