문제

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

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

출력

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

풀이

접근방법

시간제한이 1초, 메모리가 128MB, 1 ≤ T ≤ 1,000, 1 ≤ M ≤ 9999 이다.

퀵 소트를 이용하여 매번 정렬을 하는것과 우선순위 큐를 사용하는것은 시간복잡도 상으로는 O(nlogn) 으로 같지만, 우선순위큐를 사용하는것이 오버헤드가 훨씬 작다.

우선순위 큐를 2개 이용하여 중간값을 쉽게 찾아보자.
임의 순서로 입력되는 수열에서 중간값을 찾는 방법 -> ( 작성 중..)
유사한문제 -> https://www.acmicpc.net/problem/1655

• 주의할 점.
  - 각 테스트케이스에 대해 M이 10보다 크다면, 여러줄에 나누어 입력된다. 출력 또한 마찬가지로 한 줄에 최대 10개 까지만 출력해야 한다.

  틀린 케이스
  1 2 3 4 5 6 7 8 9 10 11 12 -> X

  ---

  맞는 케이스
  1 2 3 4 5 6 7 8 9 10
  11 12 -> O

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	static StringBuilder sb;
	static int M;

	static PriorityQueue<Integer> minPq;
	static PriorityQueue<Integer> maxPq;
	static List<Integer> list;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		int T = stoi(in.readLine());

		minPq = new PriorityQueue<>();
		maxPq = new PriorityQueue<>(Collections.reverseOrder());
		list = new ArrayList<>();

		for (int tc = 0; tc < T; ++tc) {
			M = stoi(in.readLine());
			String[] splitedLine = in.readLine().split(" ");

			minPq.clear();
			maxPq.clear();
			list.clear();

			for (int i = 1; i <= M; ++i) {
				int cur = getMiddle(stoi(splitedLine[(i - 1) % 10]));
				if (i % 2 == 1) {
					list.add(cur);
				}
				if (i % 10 == 0 && M > 10)
					splitedLine = in.readLine().split(" ");
			}

			sb.append(list.size())
				.append("\n");

			int count = 0;
			for (Integer value : list) {
				sb.append(value)
					.append(" ");
				count++;
				if (count % 10 == 0)
					sb.append("\n");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

	private static int getMiddle(int cur) {
		if (!minPq.isEmpty() && cur > minPq.peek()) {
			maxPq.add(minPq.poll());
			minPq.add(cur);
		} else {
			maxPq.add(cur);
		}

		if (maxPq.size() > minPq.size() + 1) {
			minPq.add(maxPq.poll());
		}
		return maxPq.peek();
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}