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

1. 문제요약

1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

정수를 하나씩 외칠 때마다 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 현재까지 모은 숫자의 갯수가 짝수 개라면 중간에 있는 두 수 중에서 짝수를 말해야 한다.

 

2. 문제예제

 

3. 문제풀이(수동)

위 문제 예제 입력 1번에 대해서 문제풀이한다.

숫자를 하나씩 받을 때마다 정렬하여 중간에 있는 숫자를 출력하면 된다. 숫자가 짝수 개일때는 둘 중에 작은 숫자를 출력한다.

 

1 => 1

1, 5 => 1 (짝수이므로 둘 중에 작은 숫자)

1, 5, 2 => 2

1, 5, 2, 10 => 2 (짝수이므로 둘 중에 작은 숫자)

-99, 1, 2, 5, 10 => 2

-99, 1, 2, 5, 7, 10 => 2 (짝수이므로 둘 중에 작은 숫자)

-99, 1, 2, 5, 5, 7, 10 => 5

 

4. 팩트추출

Fact 1 : 숫자를 받을 때마다 그 리스트를 정렬하여 중간 값을 가지고 오면 문제는 쉽게 풀린다. 다만 지문에서 확인할 수 있듯이, 아래와 같이 N 이 최대 100,000 이며, 받을 때마다 정렬하면 매번 O(N) 시간이 소요된다. 이러면 시간제한인 0.1초를 해결할 수 없을 것이다. 0.1초라는 시간을 만족하려면 삽입할 때마다 정렬하는 시간도 줄여야 하고 중간 값을 탐색하는 시간도 줄여야 한다. 정렬, 탐색 시간을 모두 줄여야 한다.

 

 

 

Fact 2 : 아래 사이트에서 자바 Collection 들에 대한 시간복잡도를 모두 찾아보았다.

(Time and Space Complexity of Collections | by Yogesh Kumar | Medium)

 

 

 

 

 

이 자료구조들에서 아이템을 삽입했을 때 자동정렬해주는 자료구조는 PriorityQueue 밖에 없다. O(log N) 으로 삽입과 동시에 정렬을 하기 때문에 빠르게 수행할 수 있다. 그리고 중간 값을 찾아주는 메서드는 어느 자료구조에도 없다. 결국 탐색해야 한다. Priority Queue 의 peek O(1) 시간 복잡도를 활용할 수 있는 방안은 없을까?

 

Priority Queue 의 peek 은 우선순위가 가장 높은 아이템 하나를 뽑으므로 중간에 peek 을 가리킬 수 있도록 Priority Queue 를 두 개 준비한다면 중간값을 바로 찾을 수 있을 것이다. 우선순위는 서로 반대이므로 왼쪽이 Max Heap, 오른쪽이 Min Heap 이 되어야 한다. Max Heap 은 내림차순으로 정렬되어 있는 자료구조로 가장 큰 값이 우선순위가 높고, Min Heap 은 오름차순으로 정렬되어 있는 자료구조로 가장 작은 값이 우선순위가 높다.

 

 

매번 삽입할 때마다 정렬하므로 maxHeap 의 peek 은 절반 중 가장 큰 값이고, minHeap 의 peek 은 절반 중 가장 작은 값이다. 아이템을 minHeap 에 넣든 maxHeap 에 넣든 상관없지만, 위 구조를 만족시키려면 minHeap 의 최소값이 maxHeap 의 최대값보다 항상 크도록 만들어주어야 한다. 넣고 나서 비교하고 maxHeap peek 숫자가 크다면 바꾸어 주면 된다.

 

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. minHeap 과 maxHeap 을 절반씩 만들어 값을 번갈아 가며 넣고 peek 으로 중간값을 꺼낸다.

 

6. 소스코드

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

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

        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(minHeap.size() == maxHeap.size()) {
                maxHeap.offer(num);
            } else {
                minHeap.offer(num);
            }
            
            if(!minHeap.isEmpty() && !maxHeap.isEmpty())
                if(minHeap.peek() < maxHeap.peek()){
                    int tmp = minHeap.poll();
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(tmp);
                }
            sb.append(maxHeap.peek() + "\n");
        }
        System.out.println(sb);
    }
}