문제

가운데를 말해요

풀이

중간값을 뽑을때는 자료구조를 두개 두고 작은 값이 나오면 상대적으로 작은 값을 앞으로 보내주는 작업을 하면 된다

이 문제에서 주어지는 내용중에 작은 값을 출력하라고 되어있으므로
상대적으로 작은 값을 가지는 우선순위 큐 보다 상대적으로 큰 값을 가지는 우선순위 큐의 양이 많아지면 큰 값을 가지는 우선순위 큐에서 앞에 있는 값을 하나빼줘서 반대 큐에 옮겨 담는다

참고로 큰 값을 가지는 우선순위 큐는 정렬 순서를 반대로 고정하여 오름차순으로 만들어주는 것이 이문제에서 가장 중요한 부분이다

PriorityQueue<Integer> minpq = new PriorityQueue<>();
PriorityQueue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());

minpq.add(Integer.parseInt(br.readLine());

for (int i = 1; i < n; i++) {
	int k = Integer.parseInt(br.readLine());
    
    
    if (minpq.size() < maxpq.size()) {
   		minpq.add(k);
 	} else { 
    	maxpq.add(k); 
    }

	int min = minpq.peek();
    int max = maxpq.peek();
    
 	if (min < max) {
   		minpq.poll(); maxpq.poll();
   		minpq.add(max);
        maxpq.add(min);
 	}
    sb.append(max.peek()).append("\n");
}

전체 코드

전체 코드