[백준]1655: 가운데를 말해요 - JAVA

[백준]1655: 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

풀이

처음에는 우선순위큐를 사용해서 풀려다가 우선순위큐의 메소드 중에서는 인덱스로 접근할 수 있는 메소드가 없어 ArrayList로 접근하였다. list에 숫자를 입력받아 넣어주고 정렬 후에 2로나눈 인덱스 값을 출력하도록 하였더니 시간초과가 발생하였다.

 

다시 우선순위큐로 접근을 시도하였으나 마땅한 해결방법이 떠오르지 않았다.

 

다른 분들의 풀이를 확인하면서 정말 놀라운 풀이법이라는 생각이 들었다. 바로 우선순위큐 2개를 사용하여 중앙값을 찾는 방법이었다. 최소 우선순위큐, 최대 우선순위큐를 사용해 두 큐의 원소 값이 균형을 이루도록 적절히 조절하여 최대 우선순위큐의 루트값이 항상 중앙값을 나타내도록 할 수 있다는 점이 놀라웠다.

 

논리적인 순서는 아래와 같다.

1. 최대/최소 우선순위 큐의 크기가 같다면 최대 큐에 숫자를 입력해 준다. 같지 않다면 최소 큐에 숫자를 입력해 준다.
2. 최대/최소 우선순위 큐가 비어있지 않고, 최대 큐의 루트값이 더 크다면 최소 큐의 루트값과 자리를 바꾸어 준다.
3. 최대 우선순위 큐의 루트값을 출력한다.

위와 같은 방법으로 코드를 따라가 보면 결국 최대 큐의 루트값은 항상 중앙값을 나타낸다는 것을 알 수 있다. 자료구조에 대해서도 왠만큼 잘 안다고 자부했었으나 이런 생각을 할 수 있다는 점이 놀라웠고 아직 부족한 점이 많다는 생각이 들었다. 부지런히 더 공부해야겠다..

 

코드

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
 
        int n = scan.nextInt();
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            int num = scan.nextInt();
            
            if(minHeap.size() == maxHeap.size()) maxHeap.add(num);
            else minHeap.add(num);
            
            if(!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.peek() < maxHeap.peek()) {
                int temp = minHeap.poll();
                minHeap.add(maxHeap.poll());
                maxHeap.add(temp);
            }
            sb.append(maxHeap.peek() + "\n");        
        }
        System.out.println(sb);
    }
}