[Java] BaekJoon 2696 중앙값 구하기 (골드2) (힙에 대한 이해)

문제출처: https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

 

문제이해

 

목표

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

 

풀이

흐름

Queue 2개를 만든다. 

비교적 작은 수들이 모여있는 leftQueue -> 내림차순 정렬 (큰 수 먼저 나오게)
비교적 큰 수들이 모여 있는 rightQueue -> 오름차순 정렬 (작은 수 먼저 나오게)

핵심은 홀 수 일 때 각 큐의 맨 앞의 값(대표)을 비교하는 것이 핵심 !! 
-> ex) 작은놈 중 가장 큰 대표 vs 큰놈중 가장 작은 대표 
-> 홀수 일때, 중앙값은 항상 leftQueue의 대표임 

로직

1. 짝수 일 때
   그냥 오른쪽 큐에 넣음

2. 홀수 일 때
   (1) 왼쪽큐의 대표와 오른쪽 큐의 대표를 비교, 왼쪽 대표가 더 크면 대표끼리 바꿔줌. 
   (2) 왼쪽큐의 대표를 정답에 추가 

 

소스코드

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

import static java.lang.System.in;

// https://www.acmicpc.net/problem/2696
// 힙 2개를 가지고 최대한 활용할 줄 알아야 하는 문제
public class 중앙값구하기 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder answerBuilder = new StringBuilder();

        for (int testCase = 0; testCase < T; testCase++) {
            int N = Integer.parseInt(br.readLine());
            // 정답 개수 출력
            answerBuilder.append(N / 2 + 1).append("\n");

            // 알고리즘 시작
            PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> rightQueue = new PriorityQueue<>();
            int count = 1;
            String[] strArr;

            while (N > 0) {
                strArr = br.readLine().split(" ");
                for (int i = 0; i < strArr.length; i++) {
                    int next = Integer.parseInt(strArr[i]);
                    if (count % 2 == 1) { // 홀수 일때
                        leftQueue.add(next);
                        if (!rightQueue.isEmpty()) {
                            if (leftQueue.peek() > rightQueue.peek()) {
                                int leftOne = leftQueue.poll();
                                int rightOne = rightQueue.poll();
                                rightQueue.add(leftOne);
                                leftQueue.add(rightOne);
                            }
                        }
                        answerBuilder.append(leftQueue.peek()).append(" ");
                    } else { // 짝 수 일 때
                        rightQueue.add(next);
                    }
                    count++;
                }
                if (count > 20) {
                    answerBuilder.append("\n");
                    count -= 20;
                }
                N -= 10;
            }
            answerBuilder.append("\n");
        }
        System.out.println(answerBuilder);
    }
}