백준 1655 풀이 (가운데를 말해요, 우선순위 큐)

이 문제는 우선순위 큐를 이용하여 중간에 존재하는 값을 출력하면 된다.

방법은 우선순위 큐를 2개 만들어서 푸는 문제이다.

최대 힙과 최소 힙을 사용하여 정렬을 유지하면 된다.

왜 이런 방식을 사용해야 하냐

만약 우선순위 큐에 값을 넣으면 저렇게 배열이 된다. 그래서 저 상태로는 중간값을 뽑을 수가 없다.

그런데 최대힙과 최소힙을 사용하면 중간값을 찾을 수 있다.

우선 최대힙의 [0]위치에는 최댓값 4를 가지고 최소힙의 [0]위치에는 최솟값 7을 가진다.

따라서 모든 힙이 정렬되지 않아도 중간값이 4라는 것을 알 수 있다. 따라서 새로운 입력에 대해서 최대힙의 개수와 최소힙의 개수를 동일한 비율로 맞춰주면 문제가 없다.

 

그러나 새롭게 입력되는 값이 -99인경우 최소힙에 3개의 값이 들어있기 때문에 -99는 최소힙에 삽입되고 유지해오던 중간값이 깨지게 된다.

 이러한 경우에는 최대힙과 최소힙의 [0]값을 서로 교환하여 값의 일관성을 유지시켜주어야 한다.

그러면 -99는 최대힙안에 들어가서 최대힙의 [0]에는 3이 새롭게 올라오고 최소힙에는 4가 최솟값으로 올라온다.

이러한 원리를 이용하여 코딩에 들어가면 된다.

정리를 하면 다음과 같다.

1. 최대힙과 최소힙을 활용하여 중간값의 일관성을 유지한다.

2. 새로운 입력이 들어올때 최대힙과 최소힙의 개수를 서로 동일하게 만들어 준다.

3. 최대힙의 최댓값과 최소힙의 최솟값을 비교하여 최댓값보다 최솟값이 더 작으면 서로 교환한다.

(단, 이때 최대힙을 구현하기 위해 음수로 넣는 트릭을 사용해 준다.)

import sys
import heapq

n = int(input())
heapr=[] # 최대힙
heapl=[] # 최소힙
for _ in range(n):
    t = int(sys.stdin.readline())
    if len(heapl) == len(heapr):
        heapq.heappush(heapl, -t)
    else:
        heapq.heappush(heapr, t)
    if heapr and -heapl[0] > heapr[0]:
        #교환
        tmp = heapq.heappop(heapr)
        tmp2 = -heapq.heappop(heapl)
        heapq.heappush(heapl, -tmp)
        heapq.heappush(heapr, tmp2)
    print(-heapl[0])