이번에 풀어본 문제는
백준 2696번 중앙값 구하기 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<Integer> map;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> minQ;
        PriorityQueue<Integer> maxQ;
        StringBuilder sb = new StringBuilder();
        while(T-- > 0)
        {
            map = new ArrayList<>();
            int N = Integer.parseInt(br.readLine());
            sb.append((N+1)/2).append("\n");
            // N이 10 이상
            while(N > 9)
            {
                st = new StringTokenizer(br.readLine());
                getList(10);
                N -= 10;
            }
            // 나머지 or 10 미만
            if(N > 0)
            {
                st = new StringTokenizer(br.readLine());
                getList(N);
            }
            minQ = new PriorityQueue<>(Collections.reverseOrder());
            maxQ = new PriorityQueue<>();

            int flag = 1;
            for(int next : map)
            {
                if(minQ.size() == maxQ.size()) minQ.add(next);
                else maxQ.add(next);
                if(!maxQ.isEmpty())
                {
                    int left = minQ.peek();
                    int right = maxQ.peek();
                    if(left > right)
                    {
                        maxQ.add(minQ.poll());
                        minQ.add(maxQ.poll());
                    }
                }
                if((flag % 2) > 0) sb.append(minQ.peek()).append(" ");

                flag++;
                // 10개 찍었으면 줄바꿈
                if(flag > 19)
                {
                    sb.append("\n");
                    flag = 0;
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
    static void getList(int n)
    {
        for(int i = 0; i < n; i++)
        {
            map.add(Integer.parseInt(st.nextToken()));
        }
    }
}

📝 풀이

N 크기의 수열이 입력될 때, 홀수번째 순서마다 현재까지 입력받은 부분수열의 중앙값을 출력하는 문제입니다.
최댓값과 최솟값을 우선순위로 갖는 큐를 두개 만들고, 둘 중 하나의 peek값이 항상 중간값을 갖도록 유지시키면 됩니다.저는 최댓값을 우선순위로 갖는 minQ의 peek를 중간값으로 두었습니다.
minQ는 항상 중간값 이하의 값들을 포함하며, 반대로 maxQ는 중간값을 초과하는 값들을 갖습니다. 따라서 홀수번째 입력을 완료한 이후 minQ의 peek값은 항상 중간값을 가질 수 있게됩니다.
양쪽 큐의 크기가 같은시점, 즉 홀수번째 입력에서 minQ에 값이 들어가야 중간값이 peek에 위치할 수 있기 때문에 사이즈를 비교하여 어느 쪽 큐에 값을 담을지 결정해주면 됩니다. 중간값을 계속 갱신해주면서 flag값이 홀수일때마다 sb에 출력값을 누적해주면 해결할 수 있습니다.

📜 후기

오래되었지만, 예전에 비슷한 문제를 풀어봤던 것이 생각나서 어렵지 않게 해결할 수 있었습니다. 혹~시 모자르셨다면 아래 문제도 풀어보시면 좋을 것 같아요!
https://www.acmicpc.net/problem/1655