중앙값 구하기

문제 설명

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

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

홀수 숫자 아니고 홀수 번째이다.

TRY

지속적으로 정렬하면서 체크했지만 FAIL

풀이

두 개의 우선순위 큐를 이용한 풀이 [MaxHeap, MinHeap]

• MaxHeap에는 큰 숫자를 넣는 것이 아니라 작은 숫자를 넣어줌(중간에 스왑 과정이 있음)

 

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

		int repeat = Integer.parseInt(reader.readLine());
		StringBuilder answer = new StringBuilder();

		for (int i = 0; i < repeat; i++) {

			PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
			PriorityQueue<Integer> minHeap = new PriorityQueue<>();

			int n = Integer.parseInt(reader.readLine());
			int totalCount = n / 2 + 1;
			answer.append(totalCount).append("\n");
			List<Integer> results = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(reader.readLine());

			for (int j = 0; j < n; j++) {
				if (j!=0 && j % 10 == 0) {
					st = new StringTokenizer(reader.readLine());
				}

				int val = Integer.parseInt(st.nextToken());

				if (maxHeap.size() == minHeap.size()) {
					maxHeap.offer(val);
				} else {
					minHeap.offer(val);
				}

				if (!minHeap.isEmpty()) {
					if (maxHeap.peek() > minHeap.peek()) {
						int t1 = maxHeap.poll();
						int t2 = minHeap.poll();

						maxHeap.offer(t2);
						minHeap.offer(t1);
					}
				}

				if (j % 2 == 0) {
					results.add(maxHeap.peek());
				}
			}

			for (int j = 0; j < results.size(); j++) {
				if (j!=0 && j % 10 == 0) {
					answer.append("\n").append(results.get(j)).append(" ");
				} else {
					answer.append(results.get(j) + " ");
				}
			}

			answer.append("\n");
		}

		System.out.println(answer);
	}