[ALGOSPOT] 알고스팟 RUNNINGMEDIAN 변화하는 중간값(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 RUNNINGMEDIAN 변화하는 중간값

(Python)

(글쓴날 : 2020.06.04)

 

---

* ALGOSPOT, 알고스팟 RUNNINGMEDIAN 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 RUNNINGMEDIAN 변화하는 중간값

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN

algospot.com :: RUNNINGMEDIAN

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

수열의 값들이 차례로 주어질 때, 매 차례 중간 값의 합을 구하는 문제입니다.

만약 수열의 길이가 짝수일 경우 두 중간 값 중 작은 값으로 계산하며, 이 문제의 경우 입력 데이터가 바로 주어지지 않고 코드 내에서 생성해야 하는 온라인 알고리즘 형태입니다.

 

저의 경우, 우선순위 큐를 이용했으며, Python을 사용했습니다.

먼저, 최소힙 기반과 최대힙 기반의 우선순위 큐 2개를 만들었습니다.

그 후, 값이 주어질 때마다 최대힙 기반의 우선순위 큐에 저장한 뒤, 만약 해당 값이 최소힙 기반의 루트 값보다 클 경우 서로의 루트 값을 바꾸어, 최종 수열의 중간 값이 항상 최대힙 기반 우선순위 큐의 루트에 존재하도록 구현하여 문제를 해결했습니다.

단, 주어진 값이 1개일 경우엔 비교를 할 수 없으므로, 조건문을 사용하여 예외 처리했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq as hq
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    N, a, b = map(int, input().split())
    minHq = []
    maxHq = []
    value = 1983
    sumValue = 0
 
    for i in range(N):
        if len(minHq) == len(maxHq):
            hq.heappush(maxHq, -value)
        else:
            hq.heappush(minHq, value)
 
        if not i:
            sumValue += -maxHq[0]
            value = (value * a + b) % 20090711
            continue
 
        if -maxHq[0] > minHq[0]:
            t1 = -hq.heappop(maxHq)
            t2 = -hq.heappop(minHq)
            hq.heappush(maxHq, t2)
            hq.heappush(minHq, t1)
        
        sumValue += -maxHq[0]
        value = (value * a + b) % 20090711
    
    print(sumValue % 20090711)

---