[백준] 1655번 : 가운데를 말해요

문제

 

 

접근 방식

수가 하나씩 추가될 때마다 현재까지의 수 중에서 중간값을 출력해야 하고

현재까지 부른 수가 짝수 개면 중간값은 둘 중 더 작은 수를 출력한다.

 

무식하게 생각하면 매번 수를 부를 때마다 정렬해서 중간 인덱스를 출력하는

방법을 떠올릴 수 있지만 문제의 제한 시간과 입력을 생각하면 불가능하다.

 

최소힙과 최대힙 우선순위 큐를 각각 하나씩 만들어서 특정 상황에 맞게

수를 저장하고 꺼내는 방식으로 효율적으로 풀 수 있는 문제다.

 

예를 들어 현재까지 주어진 수가 짝수 개일 때를 생각해 보면

현재 수가 이전까지의 중간값보다 작은 경우를 살펴보면 다음과 같다.

4 5 10 (11) 12 15 20	// 중간값 11
>> 6 이 입력으로 들어옴
4 5 6 (10 11) 12 15 20 // 중간값이 두개지만 더 작은 10을 선택

 

짝수일 때는 중간 값이 두 개가 될 수 있고 이 중에서 가장 작은 첫 번째 값을

골라야 하기 때문에 이 때는 최대힙에서 값을 꺼내 중간값으로 바꿔주고

이전의 중앙값을 최소힙에 다시 넣어준다.

최대힙 6 5 4
중간값 10
최소힙 11 12 15 20

 

위와 같이 최대힙, 중간값, 최소힙이 구성된다.

 

즉, 최대힙에서는 중간값보다 작은 값들을, 최소힙에서는 중간값보다 큰 값들을

정렬된 상태로 꺼낼 수 있으니 입력받은 수가 중간값보다 큰지 작은지에 따라

상황에 맞게 수를 꺼내고 저장하면 매번 정렬을 하지 않고 중간값을 알 수 있다.

 

풀이

public class Main {

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

		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> right = new PriorityQueue<>();
		PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());

		int center = Integer.parseInt(br.readLine());
		sb.append(center).append("\n");

		for (int i = 2; i <= n; i++) {
			int x = Integer.parseInt(br.readLine());

			if (i % 2 == 0) {
				if (center > x) {
					left.offer(x);
					right.offer(center);
					center = left.poll();
				} else {
					right.offer(x);
				}
			} else {
				if (center <= x) {
					right.offer(x);
					left.offer(center);
					center = right.poll();
				} else {
					left.offer(x);
				}
			}

			sb.append(center).append("\n");
		}

		System.out.println(sb);
	}
}