[백준] 1655번. 가운데를 말해요 (Java)

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

1655번: 가운데를 말해요

 

 

입력 값이 계속 주어질 때 해당 숫자의 가운데 값을 출력하는 문제 

 

우선순위 큐를 2개 사용해서 하나는 내림차순(max heap), 하나는 오름차순 (min heap) 으로 사용해서 해결했다. 

---

 

풀이

1. 우선 주어진 입력 값을 숫자에 상관없이 큐에 번갈아가면서 추가한다. 

2. 출력은 max heap 의 루트 값을 출력하기에 max heap 에 있는 값은 min heap 에 있는 값보다 작아야 한다. 

3. 우선순위 큐를 넣고 마지막에 min heap 에 있는 값과 max heap 에 있는 값을 비교하여 재정렬 해준다. 

 

*주의

N 값이 크기 때문에 바로바로 출력하면 시간초과 난다. 

StringBuilder를 사용하도록 하자 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;


public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Queue<Integer> queue1 = new PriorityQueue<>(Collections.reverseOrder());
        Queue<Integer> queue2 = new PriorityQueue<>();
        
        StringBuilder builder = new StringBuilder();
        
        for (int i = 0; i<n; i++) {
            int tmp = Integer.parseInt(reader.readLine());
            
            if (queue1.size() == queue2.size()) {
                queue1.add(tmp);
            } else {
                queue2.add(tmp);
            }
            
            if (queue1.size() > 0 && queue2.size() > 0 && queue1.peek() > queue2.peek()) {
                int tmp1 = queue1.poll();
                int tmp2 = queue2.poll();
                queue1.add(tmp2);
                queue2.add(tmp1);
            }
            
            builder.append(queue1.peek()).append("\n");
        }
        System.out.println(builder);
    }
}