[Python] 백준 1655 - 가운데를 말해요

백준 1655 - 가운데를 말해요

문제

코드

import sys
import heapq

input = sys.stdin.readline;

right = []
left = []
N = int(input())

for i in range(0, N):
    num = int(input())
    if len(right) == len(left):
        if len(left) != 0:
            if num < left[0][1]:
                heapq.heappush(right, heapq.heappop(left)[1])
                heapq.heappush(left, (-num, num))
            else:
                heapq.heappush(right, num)
        else:
            heapq.heappush(right, num)

    else:
        if num <= right[0]:
            heapq.heappush(left, (-num, num))
        else:
            right_num = heapq.heappop(right)
            heapq.heappush(left, (-right_num, right_num))
            heapq.heappush(right, num)

    if i % 2 == 0:
        print(right[0])
    else:
        print(left[0][1])

해설

1. heapq를 사용했다.

2. 힙을 왼쪽, 오른쪽으로 나눠서 저장해준다.
   -> left는 작은값, right는 큰값을 넣어주고 항상 right의 길이가 크거나 같도록 만들어준다.
   -> 따라서 num이 입력됐을 때 right의 값들이 항상 클 수 있도록 비교해준 후에 알맞은 곳에 넣어준다.

3. 각각 힙의 첫번째 원소를 꺼냈을 때가 중간값이기 위해 왼쪽힙은 최대힙으로 저장해준다.

4. 전체 원소의 개수가 짝수개일 때는 중간 두 값 중에서 작은 값이므로 왼쪽에서 꺼내서 출력해주고 홀수개일때는 오른쪽에서 꺼내서 출력해준다.

5. 처음에 right, left를 나누지 않고 그냥 쉽게 풀었더니 시간초과가 났다....
   다음 코드는 시간 초과가 난 코드이다.

import sys
import heapq

input = sys.stdin.readline;


def findMiddle(mid):
    for _ in range(1, mid):
        heapq.heappush(tmp_heap,heapq.heappop(heap))

    print(heap[0])
    for _ in range(1, mid):
        heapq.heappush(heap,heapq.heappop(tmp_heap))


heap = []
tmp_heap=[]
N = int(input())

for i in range(1, N + 1):
    num = int(input())
    heapq.heappush(heap, num)
    findMiddle(int((i+1) / 2))