[BOJ 1655] 가운데를 말해요(Java, Time Complexity)

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

## 시간복잡도

---

이 문제를, 단순히 정렬을 통해서 가운데를 찾는다고 생각하면, 시간복잡도는 N * N * logN이 된다.

 

 

N의 범위는 100,000이므로 제한 시간안에 문제를 푸는 것이 불가능하다.

 

 

가운데를 알기 위해서는, 주어진 값들을 항상 관리하고 있어야 한다.

 

 

새로운 값을 logN만에 삽입할 수 있는 값이 필요하다.

 

 

이진 탐색을 통해서, 위치를 찾을 수도 있지만 우선순위큐를 통해서 문제를 해결할 수 있다.

 

 

 

 

## 접근법

---

우선순위큐 한 개를 써서 문제를 해결할 수 있을까?

 

 

push 연산은 logN이 보장되지만, 가운데를 찾기 위해서는 우선순위큐의 값을 탐색해야 한다.

 

 

우선순위큐는 값을 탐색할 수 없을 뿐더라, 탐색을 한다며 어레이리스트를 이용해 이분탐색을 하고 삽입하는 방식으로 코드를 작성하는 것이 낫다.

 

 

우선순위큐 두 개를 써서 좀 더 간단하게 문제를 풀어보자.

 

 

두 개의 우선순위큐는 오름차순과 내림차순으로 구성해야하며, 개수가 같거나 1개가 차이나야 한다.

 

 

값이 삽입된 이후 우선순위큐들의 Top을 확인하여, 두 우선순위큐의 Top이 Swap되어야 하는지 확인해야 한다.

 

 

확인을 하는 것이 오름차순의 우선순위큐의 Top이 가운데 값을 가질 수 사실을 증명하게 된다.

 

 

 

 

## 해설코드

---

 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, num, i1, i2;
    static PriorityQueue<Integer> pq1 = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> pq2 = new PriorityQueue<>();
    
    public static void main (String[] args) throws java.lang.Exception
    {
        N = Integer.valueOf(br.readLine());
        
        for(int i = 0; i < N; i++){
            num = Integer.valueOf(br.readLine());
            
            if(pq1.size() <= pq2.size())
                pq1.add(num);
            else
                pq2.add(num);
            
            if(pq1.size() != 0 && pq2.size() != 0){
                if(pq1.peek() > pq2.peek()){
                    i1 = pq1.poll();
                    i2 = pq2.poll();
                    
                    pq1.add(i2);
                    pq2.add(i1);
                }
            }
            
            bw.write(pq1.peek() + "\n");
        }
        
        bw.flush();
    }
}