백준 1655 가운데를 말해요

백준 1655 가운데를 말해요

구현전 생각

ArrayList를 이용하여 입력받은 후 list의 배열의 길이/2-1을 통해서 가운데 값을 찾아내는 방식

아쉬운 점

계속해서 입력이 들어와서 배열을 정렬해주는데 많은 시간이 소요되서 시간초과

=> 해결방법으로 우선순위 큐를 사용하여서 해결하고자 생각
하지만 maxheap, minheap을 이용하여 중간값을 찾는 방법을 생각하지 못하여서 우선순위 큐를 이용한 중간값 찾는 법을 참조함

우선, maxheap과 minheap을 이용한다
maxheap의 경우 배열로 치면 0~mid까지의 값을 가지고
minheap의 경우 배열로 치면 mid~end 까지의 값을 가지고 있다 이때, 매번 maxheap의 최대값을 출력하여 중간값을 찾아 내는 방식을 이용한다.

코드

package argorithm_study_june;


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

public class backjoon_1655_가운데를말해요 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>((o1,o2)->o2-o1);
		PriorityQueue<Integer> minheap = new PriorityQueue<Integer>((o1,o2)->o1-o2);
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			
			if(maxheap.size()==minheap.size()) 
				maxheap.add(num);
			else
				minheap.add(num);
			if(!maxheap.isEmpty()&&!minheap.isEmpty()) {
				if(maxheap.peek()>minheap.peek()) {
					int temp = minheap.poll();
					minheap.add(maxheap.poll());
					maxheap.add(temp);
				}
			}
			sb.append(maxheap.peek() + "\n");
			
		}
		System.out.println(sb);
	}
}