[백준/2697/Java] 중앙값 구하기_초간단 풀이

1. 문제 이해

홀수 번째 입력을 받을 때 마다, 중앙값을 출력하는 문제

2. 문제 해석

• 중앙값 문제에서 시간제한에 걸리지 않으려면 우선순위 큐를 2개를 쓰면 된다

3. 코드

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

import static java.lang.Integer.*;
import static java.lang.System.in;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(in));

    public static void main(String[] args) throws IOException {

        int T = st(br.readLine());
        for (int testCase = 0; testCase < T; testCase++) {

            int n = st(br.readLine());
            System.out.println((n+1)/2);

            ArrayList<Integer> inputList = getInputList(n);
            PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

            int mid = inputList.get(0);
            System.out.print(mid);

            int count = 1;
            for (int j = 1; j < n; j++) {
                int num = inputList.get(j);

                if(num < mid)
                    leftQueue.add(num);
                else
                    rightQueue.add(num);

                if (j % 2 == 0) {
                    if(leftQueue.size() > rightQueue.size()) {
                        rightQueue.add(mid);
                        mid = leftQueue.poll();
                    } else if (leftQueue.size() < rightQueue.size()) {
                        leftQueue.add(mid);
                        mid = rightQueue.poll();
                    }

					//출력 형식 관리 위한 로직
                    count++;

                    if(count == 1)
                        System.out.print(mid);
                    else
                        System.out.print(" " + mid);
                }
                if (count == 10) {
                    System.out.println();
                    count = 0;
                }
            }
            System.out.println();
        }
    }


    public static ArrayList<Integer> getInputList(int n) throws IOException{
        ArrayList<Integer> inputList = new ArrayList<>();
        int lines = ((n-1)/10)+1;
        for (int line = 0; line < lines; line++) {
            String[] input = br.readLine().split(" ");
            for (String s : input) {
                inputList.add(st(s));
            }
        }
        return inputList;
    }


    public static int st(String str) {
        return parseInt(str);
    }
}

4. 코드 해설

문제의 입력, 출력에 대한 조건이 여러 개 걸려있어서 생각보다 코드가 깔끔하게 나오지 않았다..ㅠ

• leftQueue: 중앙값(mid)보다 작으면 여기에 넣는다. 내림차순 큐

• rightQueue: 중앙값(mid)보다 크면 여기에 넣는다. 오름차순 큐

• 로직:

  • 한 번에 하나씩 수를 입력 받는다

  • 현재의 중앙값보다 작으면 leftQueue에, 크면 rightQueue에 넣는다

  • 홀수 번째 수를 입력 받았을 때 나올 수 있는 상황은 3가지다.

    1. leftQueue.size() > rightQueue.size()

    2. leftQueue.size() < rightQueue.size()

    3. leftQueue.size() = rightQueue.size()

    1번 상황의 경우 기존의 중앙값은 rightQueue에 넣어주고, leftQueue에서 하나를 뽑아서 새로운 중앙값으로 삼아주면 된다.
    2번 상황에서는 1번 상황의 반대를 취해주면 되고, 3번의 경우에는 아무 것도 하지 않아도 된다.

5. 개선안

• BufferedWriter를 사용하면 System.out.println으로 출력을 찍는 것 보다 시간을 단축할 수 있다