BOJ 1655 가운데를 말해요

https://www.acmicpc.net/problem/1655

문제

백준이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

---

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

---

예제 입력 1

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5

---

코드

문제의 요구사항 자체는 매우 간단했다.

정수를 입력받을 때마다 그때까지 입력받은 정수 중 중간값을 출력하면 되는 것이었다.

하지만 중간값을 쉽게 구하기 위해 매번 정수를 입력받을 때마다 배열을 정렬된 상태로 유지시키는 부분에서 막혔다.

매번 정수를 입력받고 정렬시키면 원하는 출력값을 얻을 수는 있겠지만, 일반적인 정렬 알고리즘을 사용하면 시간 제한이 0.1초이기 때문에 시간 초과가 날 것 같았다.

그래서 고민 끝에 생각해낸 해결 방법은 두 가지 였다.

1. 이분 탐색으로 새로 입력받은 정수가 들어가야 할 위치를 찾아 insert 해서 항상 정렬된 상태로 배열을 유지하고 바로 중간값을 찾는 방법
2. 작은 값을 우선순위로 가지는 우선순위 큐와 큰 값을 우선순위로 가지는 큐를 사용해서 두 큐의 원소 수를 비슷하게 유지시켜주고, 큐에서 peek 해서 중간값을 찾는 방법

1번 방법은 일반적으로 생각할 것 같은 방법이기 때문에 2번으로 구현해봤다.

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

        // 중간값보다 작거나 같은(Little or Equal) 정수들을 저장하기 위한 우선순위 큐
        PriorityQueue<Integer> leHalf = new PriorityQueue<>(Comparator.reverseOrder());
        // 중간값보다 큰(Greater) 정수들을 저장하기 위한 우선순위 큐
        PriorityQueue<Integer> gtHalf = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());
        while (N-- > 0) {
            int input = Integer.parseInt(br.readLine());
            
            if (leHalf.size() <= gtHalf.size()) {
                gtHalf.offer(input);
                leHalf.offer(gtHalf.poll());
            } else {
                leHalf.offer(input);
                gtHalf.offer(leHalf.poll());
            }

            answer.append(leHalf.peek()).append('\n');
        }

        System.out.println(answer);
    }
}