[백준] 가운데를 말해요

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

1655번: 가운데를 말해요

Heap을 사용하는 문제입니다. 

 

문제부터 요약해보면, 숫자를 이야기 할 때 마다 이전에 이야기 한 숫자들과 종합해 오름차순으로 정렬 되었다고 생각할 때, 가운데를 return해야합니다. 

예시를 문제에서 주었는데 만약 1,3,5,2를 이야기 한다면

[1]

[1,3]

[1,3,5]

[1,2,3,5]

각각 이런 상황으로 정렬이 되기에 1,1,3,2를 return하여야 합니다. 자세한 example은 위의 링크를 읽어보시길 바랍니다. 

 

올바르지 않은 solution과 그것이 잘 작동하지 않는 이유를 이야기 하고, 정답을 설명해 보겠습니다. 

 

<Solution-오답>

문제를 가장 처음 보았을 때 python library에 이러한 것이 있지 않을까 생각하였습니다. 

그래서 인터넷을 조사한 결과 sorted list에 item을 넣어주는 library가 있는 것을 알게 되었습니다. 

https://stackoverflow.com/questions/8024571/insert-an-item-into-sorted-list-in-python

Insert an item into sorted list in Python

실제로 이 글을 읽어보면 이 문제는 굉장히 간단해 보입니다. 

<input>

import bisect 
a = [1, 2, 4, 5] 
bisect.insort(a, 3) 
print(a)

<output>

[1,2,3,4,5]

python은 자체 bisect라는 library에서 sorted list에 올바르게 넣는 방법을 제공함을 알 수 있었습니다. 그래서 처음 구현한 코드는 다음과 같습니다. 

import bisect
import sys

# num = int(input())
num = int(sys.stdin.readline())
total_len = 0
list_ = []

for i in range(num):
    bisect.insort(list_, int(sys.stdin.readline()))
    total_len+=1
    # print(f'index : {(total_len-1)//2}')
    print(list_[(total_len-1)//2])

하지만 당연히 시간초과가 나면서 테스트를 통과하지 못하는 것을 알 수 있었습니다. Library니까 최적의 상태로 할 수 있게 해두지 않았을까 라는 안일한 생각이었습니다. 한번 살펴봅시다. 

 

https://docs.python.org/3/library/bisect.html?highlight=bisect#module-bisect 

bisect — Array bisection algorithm — Python 3.10.4 documentation

위의 글은 python document의 bisect library에 대한 설명입니다. 이것을 자세히 읽어보면 다음과 같은 문장이 존재합니다. 

이 library는 new element의 append하는 지점을 O(logn)의 time complexity로 찾아주지만, list와 같은 자료구조의 O(n)의 insertion time complexity 때문에 옳게 작용하지 못한다는 이야기입니다. (dominated됨) 

https://stackoverflow.com/questions/53023380/bisect-insort-complexity-not-as-expected

bisect.insort complexity not as expected

그러면 이 방법이 잘못 되었으므로 이 문제는 어떻게 풀어야 할까요? 더불어서 백준의 문제들을 풀다 궁금증이 생긴 것이 있는데 input을 받는 함수들이 굉장히 여러개가 존재합니다. 각각 어떤 것을 사용하는 것이 빠른지 등에 대한 이야기도 추후 알아보고 포스팅 해볼 생각입니다. 

 

<Solution-정답>

Heap을 사용하면, push와 pop을 O(logn)의 time complexity로 list보다 빠르게 할 수 있습니다. 더군다나 중간값을 계속 찾아야 하는 이 문제에서는 heap처럼 priority를 기반으로 값을 pop해주는 자료구조는 굉장히 유리하게 작용 할 수 있습니다. 

 

그렇다면 어떤 식으로 아이디어를 생각해야 할까요? 

우선 leftheap과 rightheap을 둡니다. 

다음과 같이 크기순으로 heap안에 들어가게 된다고 생각합시다. 그러면 현재 상황에서는 중간원소로 무슨 값을 말해야 할까요?

바로 10입니다. 10을 이야기하기 위해서는 leftheap의 가장 큰 원소이므로 leftheap을 maxheap으로 구성해줍니다.

이제 이곳에 8이라는 숫자가 들어가야 한다고 생각해봅시다. 그러면 leftheap에 8을 넣어주면 됩니다. 이제 중간원소로 무슨 값을 말해야 할까요? 바로 8입니다. leftheap과 rightheap의 균형을 계속 맞춰주고, 원소의 갯수가 홀수개에서 leftheap이 1개 많게 하면, 우리는 leftheap에서 제일 큰 원소를 계속 return해주면 되는 것을 알 수 있습니다.

다음으로 2를 넣는다고 생각해봅시다. 2는 leftheap에 들어가야하지만 현재 균형을 맞춰주려면 rightheap에 원소를 넣을 차례입니다. 그래서 leftheap의 가장 큰 값인 10을 rightheap으로 옮겨주고, 2를 leftheap에 넣어주면 균형이 맞습니다. 이처럼 매번 input이 들어오면 균형을 맞추고, leftheap의 가장 큰 원소를 return하게 구현하면 됩니다. 

 

ps. 사실 구현을 끝낸 이후에 생각 해본 결과, 일단은 leftheap이든 rightheap이든 먼저 알맞은 위치에 append하고, 만약 균형이 맞지 않다면, 균형이 맞을때 까지 이동시키도록 코드를 구현하는 것이 조금 더 깔끔한 코드 스타일이 될 것 같습니다. 

 

실제 구현은 아래와 같습니다. 

import sys
import heapq

num = int(sys.stdin.readline())
total_len = 0

leftheap = []
rightheap = []
item = int(sys.stdin.readline())
print(item)
heapq.heappush(leftheap,(-item,item))

for i in range(num-1):
    #print(leftheap,rightheap)
    item = int(sys.stdin.readline())
    # turn to append left
    if len(leftheap) == len(rightheap):
        right_min = rightheap[0]
        if right_min >= item:
            heapq.heappush(leftheap, (-item, item))
        else: 
            temp_item = heapq.heappop(rightheap)
            heapq.heappush(leftheap, (-temp_item, temp_item))
            heapq.heappush(rightheap,item)
    # turn to append right
    else:
        left_max = leftheap[0][1]
        if item >= left_max:
            heapq.heappush(rightheap, item)
        else:
            temp_item = (heapq.heappop(leftheap))[1]
            heapq.heappush(rightheap, temp_item)
            heapq.heappush(leftheap, (-item,item))

    print(leftheap[0][1])