교대최소제곱법
[백준 파이썬 1655번 가운데를 말해요] heapq 사용법 본문
1. heapq의 힙 푸쉬는 가장 작은 숫자가 가장 앞에 존재한다.
-> 리스트명[0]은 가장 작은 숫자
-> 그래서 pop을 안하고 [0]으로 가장 작은 숫자를 엿볼 수 있다.
2. heappop은 기본적으로 가장 작은 원소를 출력한다. -> 최소힙
from heapq import heappop, heappush
N = int(input())
min_heap = []
max_heap = []
ans_ls = []
for _ in range(N):
num = int(input())
if len(min_heap) == len(max_heap):
heappush(min_heap, (-num, num))
else:
heappush(max_heap, (num, num))
if max_heap and min_heap[0][1] > max_heap[0][0]:
temp_min = heappop(min_heap)[1]
temp_max = heappop(max_heap)[1]
heappush(min_heap, (-temp_max, temp_max))
heappush(max_heap, (temp_min, temp_min))
ans_ls.append(min_heap[0][1])
print(ans_ls)https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net
'코딩테스트' 카테고리의 다른 글
| [백준 파이썬 21606번 아침 산책] 메모리 초과 해결 (0) | 2023.10.20 |
|---|---|
| [백준 파이썬 13334번 철로] heapq의 활용 (2) | 2023.10.17 |
| [2023 하반기 삼성 코테] 후기 및 분석 (1) | 2023.10.15 |
| [코테 준비] 라이브러리 없이 살아남기 (0) | 2023.10.14 |
| [백준 파이썬 1914번 하노이 탑] 하노이 탑의 이해 (0) | 2023.10.14 |
'코딩테스트' Related Articles
more
