미소를뿌리는감자의 코딩
[백준 2024/09/11] 1655번 가운데를 말해요 본문
728x90
1. 접근 방법
https://www.acmicpc.net/problem/1655
2. 문제 풀이
최소 힙과 최대 힙 2개를 이용해서 문제를 풀었다. ( 조금 힌트를 얻긴 했다.. *^^* )
블록이 홀수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop 해 최대 힙에 옮긴다. 이후, 최대 힙에서 peek를 출력하여 준다.
블록이 짝수 개 일 땐, 최소 힙에 블록을 넣고, 최솟값을 pop해 최대 힙에 옮긴다. 이후 최대 힙에서 최대를 pop하여, 최소 힙에 넣어준다.
이후, 최대힙에서 peek를 출력하여 준다.
아래 그림으로 더 자세히 설명해 보겠다.
3. 코드
import sys
import heapq
min_heap = []
max_heap = []
def find_median(i, n):
global min_heap
global max_heap
if i % 2 == 1:
heapq.heappush(min_heap, n)
heapq.heappush(max_heap, -1 * heapq.heappop(min_heap))
return max_heap[0] * -1
else:
heapq.heappush(min_heap, n)
heapq.heappush(max_heap, -1 * heapq.heappop(min_heap))
heapq.heappush(min_heap, -1 * heapq.heappop(max_heap))
return max_heap[0] * -1
if __name__ == "__main__":
for i in range(1, int(sys.stdin.readline())+1, 1):
print(find_median(i, int(sys.stdin.readline())))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/15] 1991번 트리 순회 (0) | 2024.09.15 |
---|---|
[백준 2024/09/12] 13334번 철로 (0) | 2024.09.12 |
[백준 2024/09/11] 3190번 뱀 (0) | 2024.09.11 |
[백준 2024/09/11] 2504번 괄호의 값 (0) | 2024.09.11 |
[백준 2024/09/10] 2493번 탑 (0) | 2024.09.10 |