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

문제

---

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

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

 

 

 

풀이

---

우선순위 큐를 두개 선언해서 풀었다.

 

left는 내림차순 정렬을 하고, right는 오름차순 정렬을 하였다.

가운데 수는 left 의 가장 앞에있는 수로 하였다.

 

예시에 나온 [ 1, 5, 2, 10, -99, 7, 5] 를 이용해 구현 순서를 보이면,

left	right
[1]	[]
[1]	[5]
[2, 1]	[5]
[2, 1]	[5, 10]
[2, 1, -99]	[5, 10]
[2, 1, -99]	[5, 7, 10]
[5, 2, 1, -99]	[5, 7, 10]

위와 같이 구현하면 된다.

 

left 의 개수가 right의 개수보다 2개이상 많으면 차이가 1개이하로 날때까지 right로 옮겨주었다

right 의 개수가 left의 개수보다 많으면 적거나 같아 질때 까지 left로 옮겨 주었다.

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static PriorityQueue<Integer> left , right;
	static int N;
	static StringBuilder sb = new StringBuilder();
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		left = new PriorityQueue<>(Collections.reverseOrder());
		right = new PriorityQueue<>();
		N = parseInt(br.readLine());
		
		for(int i = 0 ; i < N ; i++) {
			int num = parseInt(br.readLine());
			
			if(i == 0) {
				left.add(num);
				sb.append(num + "\n");
				continue;
			}
			
			if(left.peek() > num) {
				left.add(num);
			}
			else {
				right.add(num);
			}
			
			if(left.size() - right.size() >= 2) {
				while(left.size() - right.size() >= 2) {
					right.add(left.poll());
				}
			}
			else if(right.size() > left.size()) {
				while(right.size() > left.size()) {
					left.add(right.poll());
				}
			}
			
			sb.append(left.peek()+ "\n");
		}
		
		System.out.println(sb);
	}
}