[BaekJoon] 1655번 가운데를 말해요. (Java) 문제 풀이 [Gold 2]

문제

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

1655번: 가운데를 말해요

 

어떻게 풀 것인가?

이 문제는 우선순위 큐(PriorityQueue)를 사용하여 효율적으로 중간값을 찾는 문제이다.

기본적으로 2개의 우선순위 큐(MinHeap, MaxHeap)를 활용하면 쉽게 해결할 수 있다.

 

MaxHeap (왼쪽 그룹)

• 중간값을 기준으로 작거나 같은 값들을 저장.
• 최댓값을 빠르게 구하기 위해 내림차순 정렬.
• PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

MinHeap (오른쪽 그룹)

• 중간값을 기준으로 큰 값들을 저장.
• 최솟값을 빠르게 구하기 위해 오름차순 정렬.
• PriorityQueue<Integer> minHeap = new PriorityQueue<>();

 

각 삽입 연산에 대해 우선순위 큐는 O(logN)

N개의 숫자가 들어오므로 총 O(N logN)

최대 100,000개의 숫자가 주어져도 충분히 해결 가능

 

풀면서 놓쳤던점

1. 우선순위 큐를 하나만 사용할 경우, 중간값 유지가 어려움.
   • 하나의 PriorityQueue만 사용하면, 중간값을 찾으려면 정렬된 리스트를 유지해야 한다.
   • 그러나 삽입 시마다 정렬하는 것은 비효율적 (O(NlogN))
2. Swap을 고려하지 않으면 중간값이 깨질 수 있음.
   • 항상 MaxHeap의 루트가 MinHeap의 루트보다 작아야 한다.
   • 그렇지 않으면 두 개의 힙에서 peek 값을 교환해야 한다.

.

이 문제를 통해 얻어갈 것

우선순위큐에 대한 정리

https://superohinsung.tistory.com/242

[DataStructure] Priority Queue(우선 순위 큐) feat. JAVA

 

내 코드 

1. 두 개의 큐 크기가 같다면 MaxHeap에 추가
   • 중간값을 MaxHeap의 peek() 값으로 유지해야 하기 때문.
2. 두 개의 큐 크기가 다르면 MinHeap에 추가
   • MaxHeap이 항상 MinHeap보다 크기가 같거나 1개 더 많아야 한다.
3. 추가한 후 MaxHeap과 MinHeap의 peek()을 비교하여 Swap 처리
   • MaxHeap.peek() > MinHeap.peek() 이면 두 값을 교환해야 함.
4. 출력은 항상 MaxHeap.peek() 값을 반환
   • 현재 입력된 숫자 중 중간값은 항상 MaxHeap의 root 값.

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));
        StringBuilder sb = new StringBuilder();
        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.offer(num);
            } else { 
                minHeap.offer(num);
            }

            if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
                if (maxHeap.peek() > minHeap.peek()) {
                    int temp = maxHeap.poll();
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(temp);
                }
            }
            
            sb.append(maxHeap.peek()).append("\n");
        }

        System.out.println(sb);
    }
}