[BOJ/Java] 1655. 가운데를 말해요

[BOJ/Java] 1655. 가운데를 말해요

https://www.acmicpc.net/problem/1655

---

문제 해석

가운데를 말해요 문제는 수열이 주어졌을 때, 각 수를 하나씩 읽어가며 현재까지의 수열에서 중간값을 출력하는 문제이다. 중간값은 수열을 정렬했을 때 가운데에 위치한 값으로, 수열의 길이가 짝수인 경우 더 작은 값을 선택한다. 이 문제는 동적으로 수열이 추가될 때마다 중간값을 효율적으로 찾아야 하므로, 우선순위 큐를 활용하여 해결할 수 있다.

풀이 과정

1. 초기 설정: 두 개의 우선순위 큐를 사용한다. 하나는 최대 힙(max heap), 다른 하나는 최소 힙(min heap)으로 구성한다. 최대 힙은 중간값보다 작은 수를 저장하고, 최소 힙은 중간값보다 큰 수를 저장한다.
2. 수열 처리: 수열의 각 수를 읽어가며 다음 과정을 수행한다:
   • 최대 힙의 크기가 최소 힙의 크기보다 작거나 같으면 최대 힙에 추가한다.
   • 그렇지 않으면 최소 힙에 추가한다.
   • 최대 힙의 최댓값이 최소 힙의 최솟값보다 크면 두 값을 교환한다.
3. 중간값 출력: 현재까지의 수열에서 중간값은 항상 최대 힙의 루트에 위치하므로, 최대 힙의 루트 값을 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine()); // 수열의 길이

        // 최대 힙 (중간값보다 작은 수)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // 최소 힙 (중간값보다 큰 수)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        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.peek() > minHeap.peek()) {
                int temp = maxHeap.poll();
                maxHeap.add(minHeap.poll());
                minHeap.add(temp);
            }

            // 중간값 출력 (최대 힙의 루트)
            bw.write(maxHeap.peek() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

시간 복잡도 분석

시간 복잡도는 O(N log N)이다. 각 수를 힙에 추가하거나 제거하는 작업은 O(log N)의 시간이 소요되며, 이를 N번 반복하기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 우선순위 큐를 활용하여 동적으로 중간값을 찾는 방법을 배울 수 있는 좋은 문제이다. 최대 힙과 최소 힙을 적절히 활용하여 중간값을 효율적으로 관리하는 방식이 인상적이었다. 특히, 두 힙의 균형을 유지하면서 중간값을 찾는 과정에서 자료구조의 중요성을 다시 한번 느낄 수 있었다. 이러한 문제는 실시간 데이터 처리나 스트리밍 알고리즘에서 유용하게 활용될 수 있을 것 같다.