가운데를 말해요

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

1655번: 가운데를 말해요

문제요약:

n개의 숫자가 계속 주어질 때 이 숫자들의 중간값을(짝수라면 두값중 작은값을) 계속 출력하라

 

난이도:

골드2

 

소요시간:

25분

 

제출횟수:

1회

 

코딩:

import sys
input = sys.stdin.readline
import heapq as hp

n = int(input())
arr= [int(input()) for _ in range(n)]
h1, h2, result  = [], [], []
#h1은 큰거순 h2는 반대
hp.heappush(h1,-arr[0])
print(arr[0])

for i in arr[1:]:
    if len(h1) == len(h2):
        #같다면 일단 왼쪽에 넣기
        hp.heappush(h1,-i)
    else:
        #다르다면 오른쪽에 넣기
        hp.heappush(h2,i)
        
    while -h1[0]>h2[0]:
        #순서가 올바지 않다면 
        temp1 ,temp2 = -hp.heappop(h1), hp.heappop(h2)
        hp.heappush(h1,-temp2)
        hp.heappush(h2,temp1)
    print(-h1[0])

옛날에 수업에서 비슷한 내용이 생각이 나서 바로 구현을 했습니다. heap으로 두개의 배열에 각 숫잘르 저장하되 왼쪽배열은 큰순서로 오른쪽은 작은순서로 저장을 하고, 지금까지 받은 숫자가 홀수 라면 반드시 왼쪽배열에 하나가 더 많게 하고, 짝수라면 양쪽에 나눠가지게 코딩을 해주었습니다. 물론 지금은 그냥 넣은 후 순서를 비교해 주었지만 분기를 좀더 자세히 나누어 양 배열의 첫번째 수와 비교하고, 홀수 짝수일때를 구분한다면 시간복잡도를 더 줄일 수 있습니다.

 

추가코드:

import sys
input = sys.stdin.readline
import heapq as hp

n = int(input())
arr= [int(input()) for _ in range(n)]
h1, h2, result  = [], [], []
#h1은 큰거순 h2는 반대
hp.heappush(h1,-arr[0])
print(arr[0])

for i in arr[1:]:
    if len(h1) == len(h2):
        if i<h2[0]:
            #짝수일때 오른쪽에서 제일 작은거보다 작다면
            hp.heappush(h1,-i)
            #그냥 왼쪽에 넣으면됨
        else:
            #짝수일때 오른쪽에서 제일 작은거보다 크다면 오른쪽에서 하나빼서 왼쪽에 넣고, 새로운걸 오른쪽에 넣어야함
            hp.heappush(h1,-hp.heappushpop(h2,i))
    else:
        if i<-h1[0]:
            #홀수일때 왼쪽에서 제일 큰거보다 작다면 왼쪽에서 하나빼서 오른쪽에 넣고, 새로운걸 왼쪽에 넣어야함
            hp.heappush(h2,-hp.heappushpop(h1,-i))
        else:
            #홀수일때 왼쪽에서 제일큰거보다 크다면 
            hp.heappush(h2,i)
            #그냥 오른쪽에 넣으면 됨
    print(-h1[0])

위에서 언급한 대로 분기를 더 나눈 코드입니다.

 

조금이지만 시간복잡도가 줄은 것 을 확인할 수 있습니다.