백준 1655번 가운데를 말해요

백준 1655번 가운데를 말해요 문제이다.

 

문제는 다음과 같다. 

이번 문제도 우선순위 큐 의 분류로 들어있는 문제로 일반 배열을 사용해서 풀면 시간초과가 나올것이다. 

 

최소 힙, 최대 힙을 통해서는 최소값, 최대값만 구할 수 있다. 

중간값을 구하기 위해서는 조금 생각을 해주어야 한다. 

이 문제에서는 이 최소 힙과 최대 힙을 둘 다 사용하여 양쪽의 갯수를 계속해서 맞춰주고

최소 힙의 첫번째 값과 최대 힙의 첫번째 값을 비교하면서 바꾸어 주면 중간 값을 구할 수 있을 것 같다.

 

코드는 다음과 같다. 

import sys
import heapq

n = int(sys.stdin.readline().strip())
minh = []
maxh = []
for i in range(n):

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

    if len(minh) == len(maxh):
        heapq.heappush(maxh, (-1 * num))
    else:
        heapq.heappush(minh, num)

    if len(minh) > 0 and minh[0] < (maxh[0]*-1):
        tmp1 = heapq.heappop(minh)
        tmp2 = heapq.heappop(maxh)*(-1)
        heapq.heappush(maxh, (-1 * tmp1))
        heapq.heappush(minh, tmp2)

    print(maxh[0]*-1)

두 힙의 갯수가 같다면 무조건 최대 힙에 넣어주고 다르다면 최소 힙에 넣어준 뒤

양쪽의 첫번째 값을 비교하여 최대 힙의 첫번째 값이 최소 힙의 첫번째 값보다 크다면 값을 바꾸어주는 코드이다. 

이름과 다르게 최대 힙에는 작은수들이, 최소 힙에는 큰 수들이 들어가게 된다. 

제출을 하면서 한번 틀렸는데 첫번째 값을 비교할 때에 최대 힙은 음수로 들어있기 때문에 -1을 곱해 비교해야 하는데

그대로 비교해서 틀렸다...

이 코드만 봐서는 이해가 안될수 있는데 힙에 대해서 더 찾아보거나 실제로 수를 넣어서 확인해보면 이해가 빠를 것이다. 

성공!