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

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

1655번: 가운데를 말해요

 

Solve

 

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

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

		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>(Comparator.reverseOrder());
		PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();

		for(int i=0; i<N; i++) {
			int a = Integer.parseInt(br.readLine());
			
			if(maxheap.size()==0) maxheap.offer(a);
			else if(maxheap.size()!=0 && maxheap.size()==minheap.size()) maxheap.offer(a);
			else minheap.offer(a);
			
			if(minheap.size()!=0&& maxheap.peek()>minheap.peek()) {
				maxheap.offer(minheap.poll());
				minheap.offer(maxheap.poll());
			}
			
			sb.append(maxheap.peek()+"\n");
			
		}
		System.out.print(sb);
	}// main end
}

 

 

 

풀이 구조

 

 

주석 

 

    for(int i=0; i<N; i++) {
        int a = Integer.parseInt(br.readLine());

        if(maxheap.size()==0) maxheap.offer(a);
         // 처음 넣는 값일 경우 maxheap부터 값을 입력한다. 
        else if(maxheap.size()!=0 && maxheap.size()==minheap.size()) maxheap.offer(a);
         // 2번째 입력 이후부터는 두 힙의 사이즈가 같으면 maxheap에 값 입력. 
        else minheap.offer(a);
         // 같지 않으면 minheap에 값 입력. 

        if(minheap.size()!=0 && maxheap.peek()>minheap.peek()) {
            // 2개 이상의 입력이 생긴 후, maxheap.peek()>minheap.peek()이면 두 값 swap
            maxheap.offer(minheap.poll());
            minheap.offer(maxheap.poll());
        }

        sb.append(maxheap.peek()+"\n");
    }