[오늘의 백준 문제] 1655번 가운데를 말해요 - 이중 힙

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

 

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

7
1
5
2
10
-99
7
5

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

1
1
2
2
2
2
5

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

 

 

---

💡 아이디어

• 중간값을 매 입력마다 빠르게 구하려면 두 개의 힙(PriorityQueue)을 사용한다.
  • leftHeap: 중간값 이하를 저장하는 최대 힙 (내림차순 정렬)
  • rightHeap: 중간값 초과를 저장하는 최소 힙 (오름차순 정렬)
• 새로운 수가 leftHeap.peek()보다 작거나 같으면 leftHeap에 넣고, 아니면 rightHeap에 넣는다.
• 두 힙의 크기를 같거나 leftHeap이 1개 더 많도록 조정한다.
• 최종적으로는 항상 leftHeap의 루트가 중간값이다. (짝수개일 때는 작은 쪽을 선택해야 하므로)

 

---

⏱️ 시간 복잡도

• 힙 연산: O(log N)
• 전체 시간 복잡도: O(N log N)

 

---

📜 자바 코드

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());

        // 중간값 이하 값을 저장하는 최대 힙 (가장 큰 값이 peek)
        PriorityQueue<Integer> leftHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 중간값 초과 값을 저장하는 최소 힙 (가장 작은 값이 peek)
        PriorityQueue<Integer> rightHeap = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            // leftHeap이 비어있거나, num이 중간값 이하일 경우 leftHeap에 삽입
            if (leftHeap.isEmpty() || num <= leftHeap.peek()) {
                leftHeap.add(num);
            } else {
                rightHeap.add(num);
            }

            // 힙 크기 균형 조정
            if (leftHeap.size() > rightHeap.size() + 1) {
                rightHeap.add(leftHeap.poll());
            } else if (rightHeap.size() > leftHeap.size()) {
                leftHeap.add(rightHeap.poll());
            }

            // 현재까지의 중간값은 항상 leftHeap의 루트
            sb.append(leftHeap.peek()).append('\n');
        }

        System.out.print(sb);
    }
}

 

---

📌 핵심 요약

• 중간값이 항상 maxHeap.peek()이 되도록 유지하는 것이 핵심
• 중간값 이하: maxHeap, 중간값 초과: minHeap
• 두 힙의 크기 균형을 맞춰야 중간값이 정확히 유지된다!

 

 

 

---

☑️ 처음 작성했던 비효율적인 풀이 (이진 탐색 이용)

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));
        int N = Integer.parseInt(br.readLine());

        List<Integer> numbers = new ArrayList<>();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            int idx = Collections.binarySearch(numbers, input);
            if (idx < 0) idx = -idx - 1;
            
            numbers.add(idx, input);
            int size = numbers.size();
            int mid = size % 2 == 0
                    ? size / 2 - 1
                    : size / 2;
            sb.append(numbers.get(mid)).append('\n');
        }

        System.out.println(sb);
    }
}

• 매 입력마다 리스트에 삽입할 위치를 이진 탐색으로 찾아 삽입 후, 중간 인덱스를 계산해서 중간값을 구하는 풀이
• 간결하고 직관적인 풀이지만, 시간 복잡도에 문제가 있음

 

---

⏱️ 시간 복잡도 분석

• 이진 탐색은 O(log N)
• 하지만 리스트의 삽입/삭제 연산은 최악의 경우 O(N) → 중간 삽입 시 요소를 뒤로 밀어야 하기 때문!
• 따라서 전체 시간복잡도는 O(N²)에 가깝다.
• N ≤ 100,000 → 최악의 경우 시간 초과 발생 가능!

 

---

✅ 결론

• 리스트의 중간 삽입은 성능이 매우 떨어진다.
  • ArrayList는 끝에 추가하는 add(element)와 get(index), set(index, element)를 제외하면 모두 O(N)
  • LinkedList는 끝에 추가하는 add(element) 제외하면 모두 O(N)
• 따라서 우선순위 큐를 이용하는 것이 더 효율적이다. 
  • 삽입(add) → O(log N)
  • 삭제(poll) → O(log N)
  • 조회(peek) → O(1)