BOJ - 1655 ) 가운데를 말해요

---

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

1655번: 가운데를 말해요

 

---

특정한 수열의 숫자가 차례대로 주어질때에, 그 중간의 값을 계속 출력하면 된다.

 

두 가지 자료구조가 있다고생각하면 편하다, 항상 루트노드에 큰값이 오게 정렬되는 Max Heap과 반대인 

 

Min Heap이 있다고 가정하면 이 둘을 붙였을때 온전한 수열이 된다고 생각한다. 

 

그러면 중간값은 각 루트의 있는 값을 비교해서 선택하면 된다.

 

우선순위큐가 이러한 구조로 정렬되어있기때문에 사용하면된다.

---

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

import org.omg.CosNaming.IstringHelper;

public class 가운데를말해요 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		PriorityQueue<Integer> pqMax = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1>o2) {
					return 1;
				} else if(o1<o2) {
					return -1;
				} else {
					return 0;
				}
			}
		});
		PriorityQueue<Integer> pqMin = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1<o2) {
					return 1;
				} else if(o1>o2) {
					return -1;
				} else {
					return 0;
				}
			}
		});
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<n;++i) {
  			st = new StringTokenizer(br.readLine());
			int now = Integer.parseInt(st.nextToken());
			INPUT(pqMax,pqMin,now);
			Balance(pqMax,pqMin);
			Query(pqMax,pqMin,now,sb);
			sb.append("\n");
		}
		System.out.print(sb.toString());
	}

	private static void Balance(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin) {
		int sizeMax = pqMax.size();
		int sizeMin = pqMin.size();
		if(sizeMax==0||sizeMin==0)return;
		if(sizeMax>sizeMin) {
			pqMin.add(pqMax.poll());
		} else if(sizeMin>sizeMax) {
			pqMax.add(pqMin.poll());
		}
	}

	private static void Query(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin, int now, StringBuilder sb) {
		if(pqMax.isEmpty()) {
			sb.append(pqMin.peek());
			return ;
		} else {
			if(((pqMin.size()+pqMax.size())&1) ==0) {
				int left = pqMin.peek(); int right = pqMax.peek();
				sb.append(left > right ? right : left);
			} else {
				if(pqMin.size()>pqMax.size()) {
					sb.append(pqMin.peek());
				} else {
					sb.append(pqMax.peek());
				}
			}
			
		}
	}

	private static void INPUT(PriorityQueue<Integer> pqMax, PriorityQueue<Integer> pqMin, int now) {
		if(pqMax.isEmpty() && pqMin.isEmpty()) {
			pqMin.add(now);
			return;
		} else if(pqMax.isEmpty()) {
			if(pqMin.peek() > now) {
				int t = pqMin.poll();
				pqMax.add(t);
				pqMin.add(now);
			} else {
				pqMax.add(now);
			}
		} else {
			if(pqMax.peek() < now) pqMax.add(now);
			else pqMin.add(now);
		}
	}
}

---