Java 1655 가운데를 말해요

 

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

1655번: 가운데를 말해요

 

---

시간 제한이 0.1초이기에 원소가 들어올 때 마다 중간값을 찾는다면 시간초과가 날 것이다.(N이 최대 100,000이기 때문에)

그래서 우선순위 큐를 두개를 사용하여 해당 문제를 풀이하였다.

 

문제의 예시처럼 1, 5, 2 10, -99, 7, 5 가 입력 값으로 주어질 때 원소 하나당 어떤 작업이 이루어지는지 살펴보겠다.

 

우선 1이 들어올 때 모든 큐에 값이 없으므로 maxHeap에 원소를 넣어준다 그럼 큐 두개의 상태는 아래와 같다.

1번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : X;

2번째 원소가 들어온 뒤 - maxHeap : 1, minHeap : 5;

3번째 원소가 들어온 뒤 - maxHeap : 1,2 minHeap : 5;

 

이때 maxHeap의 peek한 값과 minHeap의 peek한 값을 비교하여 maxHeap과 minHeap의 스왑이 일어난다.

이 과정을 거치면 두 큐에 원소가 제대로 삽입되었기에 maxHeap의 값을 peek하여 출력한다.

 

우선순위 조건이 서로 다른 두개의 큐를 사용한다면 낮은 수부터 높은 수까지 정렬된 상태로 가운데에서 원소의 접근에 걸리는 시간복잡도가 상수시간이기 때문에 해당 문제를 풀이할 수 있었다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

        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 tmp = minHeap.poll();
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(tmp);
                }
            }
            sb.append(maxHeap.peek()).append("\n");
        }

        System.out.println(sb);
    }
}