boj 1655 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

수빈이가 동생에게 숫자를 하나씩 부를 때마다 동생이 처음에 말한 수부터 현재 말한 수까지의 중간 값을 출력해야합니다.

 

이 문제는 우선순위 큐로 해결할 수 있습니다.

저는 우선순위 큐 2개(최대 힙, 최소 힙 각각 1개)를 사용하였습니다.

최대 힙에는 작은값들, 최소 힙에는 큰 값들을 저장합니다. 그리고 출력은 최대힙에서 가장 작은 수를 출력합니다.

 

출력을 최대 힙으로 사용하기 때문에 최대 힙의 크기를 더 크게 유지시킵니다.

하지만 중간 값을 구해야하기 때문에 최대 힙과 최소 힙의 크기를 같게 하거나 최대 힙의 크기가 1만큼 더 커야합니다.

 

우선 최대 힙이 비어있으면 최대 힙에 저장합니다.

그리고 최대 힙의 크기가 최소 힙과 같으면 최대 힙에 add

최소 힙의 크기가 더 작으면 최소 힙에 add를 해줍니다.

 

이 과정 이후에 최소 힙의 가장 작은 값이 최대 힙의 가장 큰 값보다 작으면 두 수를 교환합니다.

 

마지막에는 최대 힙에서 가장 큰 수를 출력하면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[];
    static int N;
 
    static void func() {
        PriorityQueue<Integer> maxq = new PriorityQueue<>();
        PriorityQueue<Integer> minq = new PriorityQueue<>();
 
        for (int i = 0; i < N; i++) {
            int x = list[i];
 
            if (maxq.isEmpty()) {
                maxq.add(-x);
                sb.append(-maxq.peek() + "\n");
                continue;
            }
 
            if (maxq.size() == minq.size())
                maxq.add(-x);
            else
                minq.add(x);
 
            if (-maxq.peek() > minq.peek()) {
                int a = -maxq.peek();
                int b = -minq.peek();
                maxq.remove();
                minq.remove();
 
                maxq.add(b);
                minq.add(a);
            }
 
            sb.append(-maxq.peek() + "\n");
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        System.out.println(sb.toString());
    }
}