백준 1655 자바 - 가운데를 말해요 문제

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

우선순위 큐를 이용해서 heap을 만들어서 처리하는 방법

 

maxheap은 큰 값이 우선

minheap은 작은 값이 우선

 

입력 값을 maxheap에 1개 추가후 minheap에 추가하면서 두개의 길이를 지속적으로 맞춰줌.

maxheap의 최대값이 minheap의 최소값보다 크다면 둘을 swap 한다.

maxheap의 최대값이 중간값이 된다.

 

문제의 예시의경우 swap이 발생하지는 않음

1 입력

[1] [ ]  → 1 출력

5 입력

[1] [5]   → 1 출력

2 입력

[1 2] [5]  → 2 출력

10 입력

[1 2] [5 10]  → 2 출력

-99 입력

[-99 1 2] [5 10]  → 2 출력

7 입력

[-99 1 2] [5 7 10]  → 2 출력

5 입력

[-99 1 2 5] [5 7 10]  → 5 출력

 

 

swap이 발생하는 예시

왼쪽[] -> maxHeap, 오른쪽[] -> minHeap

10 입력

[10] [ ]  → 10 출력

8 입력

[10][8] - swap -> [8] [10]   → 8 출력 

5 입력

[5, 8] [10]  → 8 출력

3 입력

[5, 8] [3, 10]- swap -> [3 5] [8 10]  → 5 출력

5 입력

[3, 5, 5] [8, 10]  → 5 출력

-1 입력

[3, 5, 5] [-1, 8, 10] - swap -> [-1, 3, 5] [5, 8, 10]  → 5 출력

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

// 가운데를 말해요 문제 - 1766번
public class Main{

    static int N;

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(((o1, o2) -> o2 - o1));

        N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i++) {
            // 입력 순서가 짝수인 경우 - 우선적으로 maxheap에 채움
            if(i % 2 == 0) maxHeap.add(Integer.parseInt(br.readLine()));
            // 입력순서가 홀수인 경우 - maxheap과 길이를 같게 만들기 위함
            else minHeap.offer(Integer.parseInt(br.readLine()));

            // maxheap의 최대값이 minheap의 최소값보다 크면 swap
            if(!maxHeap.isEmpty() && !minHeap.isEmpty()) {
                if(maxHeap.peek() > minHeap.peek()) {
                    int temp = maxHeap.poll();
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(temp);
                }
            }
            sb.append(maxHeap.peek()).append("\n");
        }
        System.out.println(sb.toString());
    }
}