백준 1655 파이썬

https://www.acmicpc.net/problem/1655풀이max_pq는 왼쪽 절반, 즉 중간값 이하를 담고 최대 힙으로 운용한다. (파이썬에서는 -값을 넣어 사용)min_pq는 오른쪽 절반, 즉 중간값 초과를 담고 최소 힙으로 운용한다.입력값과 max_pq, min_pq에서 하나씩 빼서 총 3개의 숫자 후보를 만들고 정렬 후 재분배한다.중간값은 항상 max_pq의 top인 -max_pq[0]이 된다.max_pq = [1e9]min_pq = [1e9]1e9를 미리 넣어둔다. 즉 힙이 비어있을때 heappop 하기 위한 임시값이다.하지만 이건 비정상적인 초기값이고, 결과적으로 정답이 이상해 질 수 도 있다.a = [A[i]]a.append(-heapq.heappop(max_pq))a.append(..

https://www.acmicpc.net/problem/1655풀이매번 새로운 수를 입력받으면, 지금까지의 수 중에서 중간값을 출력해야 한다.수의 개수가 홀수이면, 정렬했을 때 가운데 수가 중간값이고수의 개수가 짝수이면, 가운데 두 수 중에서 작은 수가 중간값이다.왼쪽 힙 (left): 최대 힙. 중간값보다 작거나 같은 값 저장 (최댓값이 top)오른쪽 힙 (right): 최소 힙. 중간값보다 큰 값 저장 (최솟값이 top)중간값 위치항상 left가 right보다 같거나 1개 많도록 유지하면,중간값은 left의 루트에 위치함 (-left[0])heapq.heappush(left, -X)우선 left (최대 힙)에 넣음 (-부호로 최대 힙을 구성)if right and -left[0] > right[0]..