one Book a Day

최대힙과 최소힙을 써 중앙 인덱스를 반출하기 쉬운 자료구조를 만든다. 양쪽 큐의 길이값 조절에 따라 중앙 인덱스뿐만아니라 일정 순위의 아이템에 접근하기도 용이하게 짤 수 있따. import sys import heapq n = int(sys.stdin.readline()) max_h, min_h = [], [] # max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입 for _ in range(n): num = int(sys.stdin.readline()) if len(max_h) == len(min_h): heapq.heappush(max_h, (-num, num)) else: heapq.heappush(min_h, (num, num)) # 왼쪽 힙의 큰값이 오른쪽..

계속 쌓이는 값들 중에서 도 뭔가 sort를 계속 해주며 중앙값을 읽어야만 할것같지만 sort를 하다가는 시간초과에 걸릴게 자명.. sort를 하는대신 최대힙과 최소힙 두개를 만들어 읽어야하는값을 그 사이에 계속 컨트롤 해주는 방식으로 힙을 운용한다. 한쪽 힙의 길이가 길어지지 않도록 같은 길이면 왼쪽에 길이가 다르면 오른쪽에 넣어 균형을 맞춰주고 읽어야하는 왼쪽 힙의 value를 기준으로 좌우 크기가 역전되면 팝, 푸시를 통해 정렬된 상태를 유지해준다. import sys import heapq n = int(sys.stdin.readline()) max_h, min_h = [], [] # max_h[0][1]값을 기준으로 큰 값은 min_h, 같거나 작은 값은 max_h에 삽입 for _ in ran..