[backjoon] 백준 1655번 가운데를 말해요 (Python, Java풀이)

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

 

 

1. 매번 정렬은 너무 느리다
   “새로운 수가 들어올 때마다 지금까지의 리스트를 정렬한 후 중간값을 꺼내자”
   → 한 번 정렬에 O(N log N), 전체 N번이면 O(N² log N)… N=10만에 절대 안 된다.
2. 중간값만 빠르게 뽑을 수는 없을까?
   • 우리가 필요한 건 전체를 정렬된 상태로 유지할 필요 없이 “지금 중간값이 뭐냐?”만 알면 된다.
   • 삽입과 중간값 조회를 모두 O(log N) 안에 해결할 수 있는 자료구조를 찾아보자.
3. 한쪽 힙만으로는 부족하다
   • 최소 힙(min-heap)이나 최대 힙(max-heap) 하나만 있으면,
     • 삽입은 O(log N) OK
     • 그러나 중간값(“k번째 원소”) 조회는 지원하지 않는다.
4. 작은 절반 vs 큰 절반, 두 개의 힙!
   1. 작은 절반은 “가장 큰 값”이 필요하니 최대 힙(max-heap)
   2. 큰 절반은 “가장 작은 값”이 필요하니 최소 힙(min-heap)
   3. “짝수 개면 둘 크기 같게, 홀수 개면 작은 절반(max-heap)에 하나 더)”
      → 이렇게만 유지하면 작은 절반의 루트(=최댓값) 이 곧 우리가 찾는 중간값
   4. 새 값 넣을 때
      • 크기 기준으로 힙 하나에 넣고
      • “작은 절반에 큰 값” 또는 “큰 절반에 작은 값”이 들어갔을 때는 서로 루트끼리 교환
        → 값 순서 도 깨지지 않게 바로잡는다.

이 문제의 핵심은, 아래와같다.

“전체 데이터를 두 그룹(절반)으로 나누고, 각 그룹의 경계값(작은 절반의 최대 / 큰 절반의 최소)을 관리하면 중간값을 곧바로 알 수 있다”

 

손코딩

Python

import heapq
import sys

input = sys.stdin.readline
N = int(input())

left = []  # 최대힙 (값 음수저장)
right = []  # 최소힙

out = []

for _ in range(N):
    x = int(input())

    # 1. 크기 기준 삽입
    if len(left) == len(right):
        heapq.heappush(left, -x)
    else:
        heapq.heappush(right, x)

    # 2. 값 순서 검사 및 교환
    if right and -left[0] > right[0]:
        a = -heapq.heappop(left)
        b = heapq.heappop(right)
        heapq.heappush(left, -b)
        heapq.heappush(right, a)

    # 3. 중간값은 left[0]
    out.append(str(-left[0]))

sys.stdout.write("\n".join(out))

 

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class P1655_가운데를_말해요 {
    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> left = new PriorityQueue<>(Collections.reverseOrder());
        // 큰 절반 관리 (최소힙)
        PriorityQueue<Integer> right = new PriorityQueue<>();

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

            // 1. 크기 기준 삽입
            if (left.size() == right.size()) {
                left.offer(x);
            } else {
                right.offer(x);
            }

            // 2. 경계값 조정
            if (!right.isEmpty() && left.peek() > right.peek()) {
                int a = left.poll();
                int b = right.poll();
                left.offer(b);
                right.offer(a);
            }
            // 중간값 누적
            sb.append(left.peek()).append("\n");
        }
        System.out.print(sb);
    }
}