Heap1 [백준] 1655번 - 가운데를 말해요 문제 풀이 및 코드 해석 (Python) 1. 문제 분석📌 문제 개요숫자가 순차적으로 입력되며, 매 순간마다 중간값을 출력해야 한다. 입력된 숫자의 개수가 짝수라면 두 수 중 작은 수를 출력해야 한다. 정렬을 수행하면 O(N log N)이 걸리므로, Heap을 이용하여 O(log N)으로 해결해야 한다. 🎯 요구사항매 순간마다 중간값을 빠르게 찾아야 한다. 정렬된 상태를 유지하면서도 효율적으로 삽입이 가능해야 한다. 중간값을 즉시 출력해야 한다. 2. 해결 방법🔹 핵심 개념"중간값을 빠르게 찾는 문제" → Heap(우선순위 큐) 활용! 두 개의 힙(Heap)을 활용하여 정렬된 상태를 유지하면서 중간값을 찾는다. Python의 heapq는 기본적으로 최소 힙(Min-Heap)이므로, 최대 힙을 만들기 위해 음수 값을 저장한다... 2025. 3. 7. 이전 1 다음
