내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
중앙값 구하기
ps:problems:boj:2696
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 중앙값 구하기 ====== ===== 풀이 ===== * [[ps:우선순위큐#Running Median]]문제. [[ps:problems:boj:1655]]와 거의 동일하므로 풀이도 그쪽을 참고. * 다만, [[ps:problems:boj:1655]]에 비해서 입출력 형식이 쓸데없이 복잡하다. 숫자들을 10개단위로 라인을 쪼개 놓아서 번거롭다. ===== 코드 ===== <dkpr py> """Solution code for "BOJ 2696. 중앙값 구하기". - Problem link: https://www.acmicpc.net/problem/2696 - Solution link: http://www.teferi.net/ps/problems/boj/2696 """ import heapq import sys INF = float('inf') def main(): T = int(sys.stdin.readline()) for i in range(T): M = int(sys.stdin.readline()) print(M // 2 + 1) max_heap = [] min_heap = [] median = INF read_count = 0 while read_count < M: nums = [int(x) for x in sys.stdin.readline().split()] for num in nums: if num < median: heapq.heappush(max_heap, -num) if len(max_heap) > len(min_heap) + 1: heapq.heappush(min_heap, -heapq.heappop(max_heap)) else: heapq.heappush(min_heap, num) if len(max_heap) < len(min_heap): heapq.heappush(max_heap, -heapq.heappop(min_heap)) median = -max_heap[0] read_count += 1 if read_count % 2: print(median, end=('\n' if read_count % 20 == 19 else ' ')) print() if __name__ == '__main__': main() </dkpr> {{tag>BOJ ps:problems:boj:골드_2}}
ps/problems/boj/2696.txt
· 마지막으로 수정됨: 2022/07/05 16:16 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로