백준 1655번 - 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

1. 순차탐색

N = int(input())
answer = []
result = [0]*N

for i in range(N):
    n = int(input())
    answer.append(n)
    answer.sort()
    l = int(len(answer)/2)
    if len(answer)%2 == 1:
        result[i] = answer[l]

    else:
        result[i] = answer[l-1]

for i in range(len(answer)):
    print(result[i])

d이거 시간초과

 

 

2. 이진탐색

import bisect

N = int(input())
answer= []
result = [0]*N
for i in range(N):
    n = int(input())
    if len(answer) == 0:
        answer.append(n)
    else:
        index = bisect.bisect_left(answer,n)
        answer.insert(index,n)
    l = len(answer)//2
    if len(answer)%2 == 1:
        result[i] = answer[l]
    else:
        result[i] = answer[l-1]

for i in range(len(result)):
    print(result[i])

파이썬은 이진탐색 모듈 bisect을 제공해준다!!

 

3.힙(우선탐색 큐)

 

3_1

import heapq

N = int(input())
maxheap = []
minheap = []
for i in range(N):
    n = int(input())
    if len(minheap) == len(maxheap):
        heapq.heappush(maxheap, -n)
    else:
        heapq.heappush(minheap, n)

    if minheap and -maxheap[0] > minheap[0]:
        max_value = -heapq.heappop(maxheap)
        min_value = heapq.heappop(minheap)
        heapq.heappush(min_value, max_value)
        heapq.heappush(max_value, -min_value)
    
    print(-maxheap[0])

이건 런타임 에러난다.... 테스트 결과는 잘 맞는데 왜그런거지... 영 모르겠어서 다른 블로그를 참고해보니 튜플을 이용해서 최대힙을 구한걸 봤다..

 

3_2

import heapq
import sys
N = int(sys.stdin.readline())
maxheap = []
minheap = []
for _ in range(N):
    n = int(sys.stdin.readline())
    if len(minheap) == len(maxheap):
        heapq.heappush(maxheap, (-n,n))
    else:
        heapq.heappush(minheap, (n,n))

    if minheap and maxheap[0][1] > minheap[0][1]:
        max_value = heapq.heappop(maxheap)[1]
        min_value = heapq.heappop(minheap)[1]
        heapq.heappush(min_value, (max_value,max_value))
        heapq.heappush(max_value, (-min_value,min_value))
    
    print(maxheap[0][1])

이것도 런타임 에러..........와이.....y....

 

아무튼 한문제로 이진탐색과 힙을 다룰 수 있어서 좋았다.