[BaekJoon] 2696 중앙값 구하기 (Java)

1.  문제 링크

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

2.  문제

요약

• 어떤 수열을 읽고, 홀수번째 수를 읽을 때마다, 지금까지 입력받은 값의 중앙값을 출력하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스의 첫 번째 줄에는 1보다 크거나 같고 9,999보다 작거나 같은 홀수인 수열의 크기 M이 주어지며 두 번째 줄부터 32비트 부호있는 정수인 원소들이 주어집니다.
  • 원소는 한 줄에 10개씩 나누어져 있습니다.
• 출력: 각 테스트 케이스에 대해 첫 번째 줄에 중앙값의 개수를 출력하고, 두 번째 줄에 홀수 번째 수를 읽을 때마다 구한 중앙값을 차례대로 출력합니다. 이 때, 중앙값들은 한 줄에 10개씩 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int M;
    static int[] nums;
    static PriorityQueue<Integer> min, max;

    static void input() {
        M = scanner.nextInt();
        nums = new int[M];
        min = new PriorityQueue<>();
        max = new PriorityQueue<>(Collections.reverseOrder());

        for(int idx = 0; idx < M; idx++)
            nums[idx] = scanner.nextInt();
    }

    static void solution() {
        sb.append(M / 2 + 1).append('\n');
        int size = 0;

        for(int idx = 1; idx <= M; idx++) {
            if(max.isEmpty()) {
                max.offer(nums[idx - 1]);
                sb.append(max.peek()).append(' ');
                size++;
                continue;
            } else if(min.size() == max.size()) {
                max.offer(nums[idx - 1]);
            } else {
                min.offer(nums[idx - 1]);
            }

            if(max.size() != 0 && min.size() != 0) {
                makeHeap(min, max);
            }

            if(idx % 2 != 0) {
                sb.append(max.peek()).append(' ');
                size++;
            }

            if(size / 10 > 0) {
                sb.append('\n');
                size -= 10;
            }
        }

        sb.append('\n');
    }

    static void makeHeap(PriorityQueue<Integer> min, PriorityQueue<Integer> max) {
        if(min.peek() < max.peek()) {
            int maxCentral = max.poll(), minCentral = min.poll();
            max.offer(minCentral);
            min.offer(maxCentral);
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();

        while(T-- > 0) {
            input();
            solution();
        }

        System.out.println(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 주어지는 원소의 개수가 홀수 개이기 때문에 중앙값의 개수는 (원소의 개수 / 2 + 1)을 통해 구할 수 있고 최소 힙과 최대 힙을 생성한 후에 최대 힙부터 번갈아가며 수를 하나씩 넣으며 중앙값을 구합니다.
• 첫 번째 원소부터 마지막 원소까지 순회하면서 아래와 같은 작업들을 수행하여 중앙값을 구합니다.
  • 만약 최대 힙이 비어있다면 최대 힙에 원소를 넣고 StringBuilder에 홀수번째 수이기 때문에 해당 원소를 추가하며 작성한 중앙값의 개수를 나타내는 size 변수를 1 증가시키고 다음 원소로 넘어갑니다.
  • 만약 최대 힙의 원소의 개수와 최소 힙의 원소의 개수가 같다면 최대 힙에 현재 원소를 넣습니다.
  • 위 두 경우 모두 아니라면 최소 힙에 현재 원소를 넣습니다.
  • 최대 힙이 비어있는 경우가 아니라면 아래 조건들을 확인합니다.
    • 만약 두 힙 모두 비어있지 않다면 최대 힙에서 가장 큰 수와 최소 힙에서 가장 작은 수를 비교하여 만약 최대 힙에서 가장 큰 수가 더 크다면 최대 힙에서 가장 큰 수를 최소 힙으로, 최소 힙에서 가장 작은 수를 최대 힙으로 맞바꿔줍니다.
    • 만약 현재 원소가 홀수번째라면 StringBuilder에 중앙값인 최대 힙의 가장 큰 수를 추가하고 size 변수를 1 증가시킵니다.
    • 만약 size / 10이 0보다 크다면 10개 이상이 되었다는 뜻이므로 줄 바꿈 기호를 StringBuilder에 추가하고 size에서 10을 뺍니다.
• 위 작업을 모든 테스트 케이스에 대해 진행한 후 StringBuilder를 출력합니다.