백준 : 1655

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

문제는 MaxHeap Minheap을 만들어서 중앙값 왼쪽 오른쪽을 관리하는 것이다.

Maxheap   mid    Minheap 이런식으로 정렬은한다고 친다면 처음 받은 중앙값을 mid로 하고 관리하면된다.

이때 처음받은 값을 기준으로 그다음값이 mid 보다 크다면 Minheap에 넣어주고

작다면 Maxheap에 넣어준다. 이때 중앙값이기 때문에 Maxheap과 Minheap 사이즈가 중요하다 전체값이 홀수라는것은 Maxheap과 Minheap의 사이즈가 같을때이다.

만약 Maxheap이 1이 Minheap보다 더크다면 정답은 Maxheap의 맨위에값이다 이때는 따라서

mid값을 Minheap으로 옮겨주고 mid를 Maxheap값으로 갱신해준다.

이렇게되면 Maxheap은 항상 Minheap보다 같거나 1작은 상태이다.

만약 Minheap이 Maxheap보다 2크다면 이번에는 오른쪽에서 왼쪽으로 옮겨준다.

이렇게하면 Minheap 사이즈는 Maxheap보다 항상 1크거다 같다가 성립한다.

 

package day0301;
 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class B1655 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        PriorityQueue<Integer> left = new PriorityQueue<Integer>(Comparator.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<Integer>();
 
        int mid = sc.nextInt();
 
        for (int n = 0; n < N - 1; n++) {
            System.out.println(mid);
 
            int tmp = sc.nextInt();
 
            if (mid < tmp) {
                right.add(tmp);
            } else {
                left.add(tmp);
            }
 
            // 오른쪽이 두개더만타면
            if (left.size() + 2 == right.size()) {
                left.add(mid);
                mid = right.poll();
            }else if (left.size() == right.size() + 1) {
                right.add(mid);
                mid = left.poll();
            }
 
        }
 
        System.out.println(mid);
 
    }
}