중앙값 구하기

문제 설명

시퀀스를 읽어 홀수를 읽으면 지금까지 입력한 값의 중앙값을 출력하는 프로그램을 작성하세요.

예를 들어 수열이 1, 5, 4, 3, 2일 때 홀수는 1, 3, 5번째 숫자이고, 1번째 숫자를 읽은 중앙값은 1번째, 3번째 숫자를 읽은 중앙값입니다. 4번째와 5번째 숫자를 읽으면 3입니다.

홀수가 아니라 홀수입니다.

시도

계속해서 확인하고 정리했습니다. 실패하다

설명

두 개의 우선 순위 큐(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);
	}