백준 1655번 Python heapq 활용

글을 쓴 계기

이 문제는 예전에 삼성SDS 대학생 알고리즘 특강 때 C++로 푼 적이 있다.
지금은 Python3이 더 익숙하기 때문에 파이썬으로 풀어보고 싶어 도전했다.
파이썬에 PriorityQueue 라이브러리를 이용해 풀어보려 했으나, PriorityQueue를 활용하면 값을 넣고 빼는 것 외에 검색이 안되어 불필요한 연산이 더 필요했다. 그래서 시간초과가 나는 것 같다!

그래서 heapq로 다시 푸느라 많이 돌아갔다 ㅎㅎ
사용해보니 heapq가 더 편리해서 기록해두려고 한다.
(벨로그 테스트용 첫 게시글이당!!)

문제 - 가운데를 말해요

https://www.acmicpc.net/problem/1655

알고리즘 의사코드

small = [] #작은 값들 트리, 최대힙
large = [] #큰 값들 트리, 최소힙

for N회:
	input 받기
	if small크기 == large크기:
    	small heap에 input 추가
    else:
    	large heap에 input 추가
    
    if small 최댓값 > large 최솟값:
    	small 최댓값과 large 최솟값 서로 바꿔줌
    
    small 최댓값 출력

실제 코드 - heapq (통과)

시간복잡도 : O(nlogn)

최대힙은 heapq에 튜플 형식으로 우선순위를 반대로 지정해서 넣어주면 된다.
ex) heapq.heappush(리스트명, (-i,i))
-i 만큼의 우선순위로 i값을 넣어준 것.

import sys
import heapq
inputt = sys.stdin.readline
N = int(inputt())
small = []
large = []

for i in range(N):
    ni = int(inputt())
    if len(small)==len(large):
        heapq.heappush(small,(-ni,ni))
    else:
        heapq.heappush(large,ni)

    if large and small[0][1] > large[0]:
        tmp_s = heapq.heappop(small)[1]
        tmp_l = heapq.heappop(large)
        heapq.heappush(small,(-tmp_l,tmp_l))
        heapq.heappush(large,tmp_s)
    print(small[0][1])

PriorityQueue 풀이 코드 (시간초과)

시간복잡도 : O(nlogn)
단점 : 각 큐의 최대, 최솟값을 검색해보기위해 꺼내서 보고 다시 넣어줌
부끄럽지만 차이를 잘 보여주는 것 같아서 올려봅니다!

import sys
from queue import PriorityQueue
inputt = sys.stdin.readline
N = int(inputt())
small = PriorityQueue()
large = PriorityQueue()

for i in range(1,N+1):
    ni = int(inputt())
    if small.qsize()==large.qsize():
        small.put((-ni,ni))
    else:
        large.put(ni)

    if not large.empty():
        s = small.get()[1]
        l = large.get()
        if s>l:
            small.put((-l,l))
            large.put(s)
        else:
            small.put((-s,s))
            large.put(l)
    mid=small.get()[1]
    print(mid)
    small.put((-mid,mid))