BOJ/1655] 가운데를 말해요

오답

n =int(input())
userSorted = [-10000,10000]

for i in range(0,n):
    u = int(input()) 
    #print(len(userSorted))

    for j in range(0,len(userSorted)-1):
        if(userSorted[j]<=u and u<=userSorted[j+1]):
            userSorted.insert(j+1,u)
            break
    print(userSorted[(len(userSorted)-1)//2])

 시간 제한에 아직 익숙하지 않아서, O(N)의 선형시간으로 삽입하며 정렬된 값의 중간값을 출력한다면 쉽게 풀 수 있을 줄 알았다. 하지만 실제 결과는 약 20배정도 더 걸렸고, 이렇게 풀이하는 게 잘못되었다는 것을 깨달았다.추가로 Search에 걸리는 O(N)을 절약하기 위해서 Peek Time을 사용하도록 최대힙, 최소힙을 병용하는 것이 효율적이라고 생각했다.따라서 왼쪽, 오른쪽을 나누어서 생각하기로 했고, 왼쪽은 최대힙으로 유지, 오른쪽은 최소힙으로 유지하여 중간값을 O(1)에 색출해 낼 수 있도록 했다.

시간 초과가 많이 나서 알고리즘의 문제인 줄 알았는데 입력의 문제였다...

자료구조 선택을 O(logN)인 것을 해야한다고 깨달았고, 우선순위에 따라서 삽입과 함께 정렬이 되는 우선순위 큐를 사용하는 것임을 알았다.

Remember : sys.stdin.readline !!!!!

Remember :

sys.stdin.readline

import sys
input = sys.stdin.readline

 

정답

import sys
import heapq
input = sys.stdin.readline

leftheap,rightheap = [],[]
n = int(input())
for i in range(0,n):
    user = int(input())
    if(len(leftheap)==len(rightheap)):
        heapq.heappush(leftheap,-user)
    else:
        heapq.heappush(rightheap,user)

    if(len(leftheap)>0 and len(rightheap)>0 and -leftheap[0]>rightheap[0]):
        temp_left = -heapq.heappop(leftheap)
        temp_right = heapq.heappop(rightheap)
        heapq.heappush(leftheap,-temp_right)
        heapq.heappush(rightheap,temp_left)
    print(-leftheap[0])