[java] 큐 / 우선순위 큐 / 힙

1. 백준 1655: 가운데를 말해요

1655번: 가운데를 말해요

Queue를 사용하여 중앙값을 찾는 방법
중앙값 기점으로 maxPq(Heap) / minPq(Heap) 이용하기
maxPq: 중앙값보다 작은 값 저장 / minPq: 중앙값보다 큰 값 저장 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> minPq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if (maxPq.isEmpty() || maxPq.peek() >= num) {
                maxPq.offer(num);
            } else {
                minPq.offer(num);
            }

            if (maxPq.size() > minPq.size() + 1) {
                minPq.offer(maxPq.poll());
            } else if (minPq.size() > maxPq.size()) {
                maxPq.offer(minPq.poll());
            }

            if (maxPq.size() == minPq.size()) {
                sb.append(Math.min(maxPq.peek(), minPq.peek())).append("\n");
            } else {
                sb.append(maxPq.peek()).append("\n");
            }
        }
        System.out.print(sb);
    }
}

 

2. 백준 12764: 싸지방에 간 준하

10% 오답으로 꽤나 고통 받았던 문제. 
이유는 내가 짠 코드가 비어있는 자리 중에서 번호가 작은 자리부터 앉는다는 조건을 만족하지 않았기 때문

많은 분들이 나와 같은문제를 겪으신 것 같아 질문게시판에  반례가 여러 개 올라와 있다. 

만약 나와 같은 난관에 봉착하시는 분들이 있다면,,, 반례 돌려보면서 조건을 모두 만족하도록 다시 코드를 짜보시길!

노션에도 반례 정리해놓긴 함 

12764번: 싸지방에 간 준하

3. 프로그래머스: 다리를 지나는 트럭

프로그래머스

⚒️자세한 풀이 및 코드는 노션에

02.22 CodingStudy- Queue | Notion