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

1. 문제

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

2. 접근 방법

인풋을 받으면서 가운데를 확인하면 백퍼 시간초과 각이었고

접근 방법이 생각나지 않아 검색을 했다.

 

이 문제는 최대힙과 최소힙을 사용해서 풀어야하는 문제였다.

 

1. 최소 힙의 값들은 모두 최대 힙보다 크도록 하고

2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.

3. 값을 넣어준 후 최대 힙과 최소 힙의 top값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크면 값을 교환해준다.

4. 최대 힙의 top값이 중간 값이된다.

3. 코드

python

import heapq, sys

N = int(input())
max_lst = []
min_lst = []
for i in range(N):
    n = int(sys.stdin.readline())
    if len(max_lst)-len(min_lst) <= 0:
        heapq.heappush(max_lst, (-n, n))
    else:
        heapq.heappush(min_lst, n)

    if max_lst and min_lst and max_lst[0][1] > min_lst[0]:
        maxtomin = heapq.heappop(max_lst)[1]
        mintomax = heapq.heappop(min_lst)
        heapq.heappush(min_lst, maxtomin)
        heapq.heappush(max_lst, (-mintomax, mintomax))

    print(max_lst[0][1])

4. 마치며

여기를 참고해서 풀었다.

regularmember.tistory.com/142

[BOJ] 1655. 가운데를 말해요

그리고 힙 관련 문제는 왜 다들 input()하면 시간초과가 뜨는지 ㅠ

얘도 앞서 풀었던 최소 힙, 최대 힙, 절댓값 힙과 마찬가지로 sys.stdin.readline()으로 입력을 받아줬따.