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

알고리즘을 다시 시작한지 얼마되지 않아 자료구조에 대한 이해가 부족해서 조금 헤맸다.

 

문제의 포인트는 다음과 같다.

1. 두 개의 힙을 사용하는 것인데 최대힙과 최소힙을 사용하는 것이다.

2. 왼쪽을 최대힙, 오른쪽을 최소힙으로 사용하고 최대힙 최소힙의 크기를 적절하게 유지하는 것이다.

 

적절하게 유지한다는 이야기는 연속된 수열을 대충 반으로 나눴을때 아래와 같이

1 2 3 / 4 5 6 과 같이 유지한다는 의미이며 문제의 조건에 따르면 중간값의 항상 최대힙의 top이 된다.

 

하나의 예를 들어서 설명해보겠다.

 

연속된 숫자가 다음과 같이 입력된다고 해보자.

1
5
2
10
-99
7
5

 

위와 같이 진행될 것이다. 그리고 추가로 최대힙의 top 값과 최소힙의 top 값은 항상 최소힙이 크거나 같도록 유지해야 한다.

그럼 알고리즘 정리를 해보겠다.

1. 힙 크기 비교
   • 최대힙의 크기와 최소힙의 크기가 같다면 최대힙에 숫자 삽입
   • 아니면 최소힙에 숫자 삽입
2. 최대힙 최소힙 top 값 비교
   • 최대힙 top ≤ 최소힙 top → continue
   • 최대힙 top > 최소힙 top → swap (최대힙 top, 최소힙 top)
3. 최대힙 top 값 출력

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    public static void main(String[] args) throws IOException {
        int n;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.comparingInt(o -> -o));

        n = Integer.parseInt(br.readLine());

        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 (!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.peek() < maxHeap.peek())
            {
                int a = minHeap.poll();
                int b = maxHeap.poll();
                minHeap.add(b);
                maxHeap.add(a);
            }
            System.out.println(maxHeap.peek());
        }
    }
}

 

본 코드의 출력 부분을 BufferedWriter로 변경하지 않으면 통과되지 않습니다.