백준 2110 java - 가운데를 말해요

문제, 입출력, 테스트케이스

1시간 3분만에 정답!

해당 문제는 아이디어 도출 : 구현 = 3 : 2 정도 시간이 걸린 문제이다. 이중 우선순위큐 문제랑은 약간 다른 느낌이지만 결국 시간 제한 0.1초 이내에 풀려면 이중 우선순위큐를 써야한다는 점이 핵심이다.

<문제 풀이/접근과정>
1. 1 <= N(입력받을 수의 갯수) <= 100,000, -10,000 <= An(입력 받은 수의 크기) <= 10,000
2. 시간제한 0.1초 = 약 1천만번의 연산 가능
3. 매 번 받은 전체의 수 중에 가운데 숫자를 출력해야하며 짝수개의 숫자가 있을 때는 중앙값은 중간의 두 수 중 작은 수 -> 홀수면 N/2, 짝수면 N/2-1번째 인덱스의 수
4. 배열을 매번 받을 때마다 정렬해서 가운데 인덱스 수를 뽑을까? -> 이러면 매번 정렬하고 뽑아야 하니 O(NlonN) *O(1) (N은 1부터 100,000) 까지라서 0.1초 내에는 안될 것 같다.
5. 이중 우선순위큐를 써볼까? 특징이 중앙값을 기점으로 좌우로 나눠지잖아? 이거다!
6. 구현해 봐야지!

중간에 친구한테 전화와서 로직이 꼬이는 바람에 더 시간이 걸렸지만 2트만에 패스!

한 번은 널포인터익셉션이 떴는데 그 이유는 왼쪽큐의 원소가 없을 때 poll()을 해버려서 그랬었다!

package boj;

import java.io.*;
import java.util.*;

public class Boj_2110 {
	// 1 1 X
	// 1 5 1 5
	// 1 2 5 2 5
	// 1 2 5 10 2 5 10
	// -99 1 2 5 10 2 -99 5 10
	// -99 1 2 5 7 10 2 -99 5 7 10
	// -99 1 2 5 5 7 10 5 -99 5 7 10
	// 홀수면 N/2, 짝수면 N/2-1번째 인덱스의 수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> rightPq = new PriorityQueue<>();
		PriorityQueue<Integer> leftPq = new PriorityQueue<>(Collections.reverseOrder());
		StringBuilder sb = new StringBuilder();
		int center = 0;
		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(br.readLine());
			if (i == 0) {
				sb.append(temp).append("\n");
				leftPq.add(temp); // 왼쪽의 제일 큰값
			} else {
				if (leftPq.size() > rightPq.size()) { // 왼쪽 큐가 오른쪽 큐 보다 더 많은 원소가 있을 때
					int leftMax = leftPq.poll();
					if (leftMax <= temp) { // 왼쪽 큐의 Max값보다 들어온 수가 더 크거나 같을 때는 오른쪽 큐에 넣으면서 가운데수는 왼쪽큐의 max
						sb.append(leftMax).append("\n");
						leftPq.add(leftMax);
						rightPq.add(temp);
					} else { // 왼쪽 큐의 Max 보다 작을 때는 왼쪽큐의 max를 오른쪽큐에 넣으면서 왼쪽 큐의 Max와 비교한 후 max보다 크면 center 아니면
								// 왼쪽큐의 max가 가운데이며 다시 넣어줌
						rightPq.add(leftMax);
						if (leftPq.isEmpty()) {
							sb.append(temp).append("\n");
							leftPq.add(temp);
						} else {
							center = leftPq.poll();
							if (center <= temp) {
								sb.append(temp).append("\n");
							} else {
								sb.append(center).append("\n");
							}
							leftPq.add(center);
							leftPq.add(temp);
						}
					}
				} else if (leftPq.size() == rightPq.size()) { // 갯수가 같을 때
					int rightmin = rightPq.poll();
					if (rightmin <= temp) {
						sb.append(rightmin).append("\n");
						leftPq.add(rightmin);
						rightPq.add(temp);
					} else {
						rightPq.add(rightmin);
						center = leftPq.poll();
						if (center <= temp) {
							sb.append(temp).append("\n");
						} else {
							sb.append(center).append("\n");
						}
						leftPq.add(center);
						leftPq.add(temp);
					}
				}
			}
		}
		sb.setLength(sb.length() - 1);
		System.out.println(sb);

	}
}

단계별로 풀기 우선순위 큐 다 풀었다!!