백준 1655번: 가운데를 말해요

문제 정보

---

 

 

1655번: 가운데를 말해요

 

핵심

---

현재까지의 수의 개수가 홀수 개인 경우 가운데에 있는 수를 택하면 됨

짝수 개인 경우에는 두개의 수 중 작은 수를 택하면 됨

 

처음에는 이런 생각으로 정렬된 배열에서의 중앙 인덱스를 구해서 중앙값을 구하면 되겠다고 생각했지만, 생각해 보니 Heap은 내부가 정렬된 상태는 아니기 때문에 이렇게 풀이하지 못했다

 

정렬된 상태를 유지하는 자료구조를 써야하나?

-> AVL 트리나 레드블랙 트리를 써야 할까도 생각했지만, 중앙 값을 구하는 것이 쉽지 않기 때문에 실패했다

 

두개의 Heap을 사용한다

왼쪽은 최대 힙, 오른쪽은 최소 힙을 사용한다

전체 수들 중 작은 반은 왼쪽 최대 힙에 들어가고, 큰쪽 반은 오른쪽 최소 힙에 들어간다

일단 중앙값을 구하는 것은 최대 힙(왼쪽)의 루트에 있는 값이므로 O(1) 에 접근이 가능할 것이다

 

어떻게 가능한가?

일단 몇가지 조건이 존재하는데 조건은 다음과 같다

• 최대 힙의 사이즈는 최소 힙의 사이즈와 같거나, 하나 더 크다
• 항상 중앙값은 최대 힙의 최대값이다
• 최대 힙의 최대값 > 최소 힙의 최소값 이라면, 두 수를 swap 한다

 

마지막, 최대 힙의 최대값 > 최소 힙의 최소값 이라면, 두 수를 swap 한다 에서 이 구조를 유지할 수 있는 방법이 나와있는데

1. 최대 힙(왼쪽)에 큰 값(반으로 나눴을 때 큰쪽에 있는 값)이 들어간 경우 루트에 해당 값이 존재할 것이다 (가장 큰 수이기 때문)
2. 최소 힙(오른쪽)에 작은 값(반으로 나눴을 때 작은 쪽에 있는 값)이 들어간 경우 루트에 해당 값이 존재할 것임 (가장 작은 수)

 

따라서 이를 swap 해주면(pop and push) 왼쪽은 작은 값들과 오른쪽은 큰 값들을 맞출 수 있다

 

풀이

---

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

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

        int N = Integer.parseInt(br.readLine());
        Queue<Integer> maxQueue = new PriorityQueue<>(((o1, o2) -> o2-o1));
        Queue<Integer> minQueue = new PriorityQueue<>();

        for(int i=0; i<N; i++) {
            int input = Integer.parseInt(br.readLine());
            if(maxQueue.size() < minQueue.size() + 1) {
                maxQueue.add(input);
            } else {
                minQueue.add(input);
            }
            if(minQueue.size() > 0 && maxQueue.peek() > minQueue.peek()) {
                int minTop = minQueue.poll();
                int maxTop = maxQueue.poll();
                minQueue.add(maxTop);
                maxQueue.add(minTop);
            }
            sb.append(maxQueue.peek()).append('\n');
        }
        System.out.println(sb);
    }
}

 

 

Source Code on GitHub

---