[Week 3] RUNNINGMEDIAN self review - ChaeheeKang-GitHub

[chaeheekang]

RUNNINGMEDIAN self review

• 파일명: PQR/RUNNINGMEDIAN/ChaeheeKang-Github.py
• 수행시간: 296ms

1. 고민 과정

처음에 최대힙과 최소힙을 구분지어 나누는 코드를 짜고 실행해본 결과 정답이 나오지 않았습니다.
문제는 maxHeap에 넣어줘야 할 값을 음수처리를 하지 않았던 거였습니다.

2. 풀이 아이디어

이 문제를 풀기위한 조건이 두가지가 존재하는데
첫번째는 최대힙의 크기는 최소힙의 크기와 같거나 하나 더 커야하며
두번째는 최대힙의 최대원소는 최소힙의 최소 원소보다 작거나 같아야 하는 것입니다.

이 두가지 조건을 토대로 코드를 작성했습니다.

3. 작성한 코드와 설명

import heapq

C=int(input())
    
for _ in range(C):
    N,a,b=list(map(int,input().split()))
    #초기 변수 선언
    ret=1983
    #최소힙과 최대힙
    minHeap=[]
    maxHeap=[]
    sum=0
    
    for _ in range(N):
        #1번 조건
        #두 문자열의 길이가 같다면 maxHeap에 -ret 값을 넣어주고
        if len(minHeap)==len(maxHeap):
            heapq.heappush(maxHeap,-ret)
        #아니라면 minHeap에 ret를 넣어주도록 합니다.
        else:
            heapq.heappush(minHeap,ret)
        
        #2번 조건
        #max에는 음수로 값을 넣어줬으니 비교를 위해 다시 음수처리(양수화)
        if minHeap and maxHeap and -maxHeap[0] > minHeap[0]:
            t1=-heapq.heappop(maxHeap)
            t2=-heapq.heappop(minHeap)
            heapq.heappush(maxHeap,t2)
            heapq.heappush(minHeap,t1)
            
        #중간값은 최대힙의 루트가 됨
        sum+=-maxHeap[0]%20090711
        ret=(ret*a+b)%20090711
    print(sum%20090711)

추가로 for문에

if a==1 and b==0:
  sum=(ret*N)%20090711
  break

을 넣어주면 시간을 아주 쪼금(4ms) 단축시킬 수 있었습니다. :)
a가 1이고 b가 0이라면 모든 값이 동일하기 때문이죠