백준 1655 문제 링크: https://www.acmicpc.net/problem/1655
📑 문제 설명
1. 숫자가 하나씩 입력됨
2. 입력 되었을 때까지의 숫자 중 중간값을 출력
3. 만약 입력된 숫자의 개수가 짝수개라면 더 작은 수를 출력
입력: 입력받는 정수의 개수 N이 주어지며 둘째줄부터 정수가 차례대로 입력됨
출력: 입력됐을 때까지의 중간값을 출력함
💡 문제 해결 방법
알고리즘: heap
하단의 참고에 달린 글을 참고하여 코드 작성
참고의 글을 요약하자면
1. max heap과 min heap을 사용한다.
2. 이 때 max heap과 min heap 을 사용할 때 숫자를 삽입하는 조건이 존재한다.
- 조건 1) max heap의 개수는 반드시 min heap과 같거나 1만큼 크다.
- 조건 2) min heap에 저장된 원소들은 max heap 에 저장된 원소보다 커야 한다.
- 이 때, 조건 1을 따라 원소를 삽입할 경우 조건 2를 위반하는 경우가 생기는데 이 때는 max heap의 top과 min heap의 top을 swap 해주면 된다.
예외처리 및 추가 내용
💻 코드
import sys
import heapq
n = int(sys.stdin.readline())
max_heap = []
min_heap = []
for _ in range(n):
num = int(sys.stdin.readline())
if len(max_heap) == len(min_heap):
heapq.heappush(max_heap, -num)
elif len(min_heap)+1 == len(max_heap):
heapq.heappush(min_heap, num)
if len(max_heap)!= 0 and len(min_heap)!= 0 and -max_heap[0] > min_heap[0]:
maxtemp = -heapq.heappop(max_heap)
mintemp = -heapq.heappop(min_heap)
heapq.heappush(min_heap, maxtemp)
heapq.heappush(max_heap, mintemp)
print(-(max_heap[0]))
💟 추가적으로 알게 된 점
