백준 1655 가운데를 말해요

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1655

이 문제는 숫자를 입력받을 때마다 사전순으로 정렬하였을 때 가운데에 있는 값을 계속 출력해주어야 하는문제이다.

풀이

난이도 : Gold II

이 문제에서 숫자를 입력받을 때마다 sort를 하여 가운데에 있는 값을 고른다면 시간초과가 난다.
따라서 이 문제에서는 Priority Queue를 두 개 사용하여 가운데에 있는 값을 구해주었다.

높은 값을 기준으로 하는 Priority Queue -> 왼쪽 (max q)
낮은 값을 기준으로 하는 Priority Queue -> 오른쪽 (min q)

왼쪽 q와 오른쪽 q에 있는 숫자의 개수를 맞춰주어 가운데 값을 q에서 바로 꺼낼 수 있도록 구현하였다.

1) max q 와 min q의 길이가 같은 경우

• max q에 값을 저장한다.
• 이 경우 모든 숫자의 개수가 홀수가 된다.

2) max q와 min q의 길이가 다른 경우 -> 즉, max q에 값이 한 개 더 들어있는 경우

• min q에 값을 저장한다.
• 모든 숫자의 개수가 짝수가 된다.

3) 방금 q에 저장한 값이 올바르게 들어갔는지 모르기 때문에 각 queue들을 업데이트해준다.

• max q 에서 값을 꺼낸다. -> 왼쪽 q 중 가장 큰 값
• min q 에서 값을 꺼낸다. -> 오른쪽 q 중 가장 작은 값
• 두 값을 비교하여 왼쪽에 있는 값이 오른쪽 값보다 크다면 서로 위치를 바꾸어 각 q에 값을 넣어준다.

4) 숫자의 개수가 홀수이든 짝수이든 max q에서 값을 꺼내어 출력해준다.

👉 python에서는 sys.stdin.readline을 사용하지 않으면 아래 코드에서도 시간 초과가 발생하니 꼭 사용해주어야 한다.

코드

import heapq
import sys

input = sys.stdin.readline
n = int(input())

max_q = []
min_q = []

results = []
for _ in range(n):
    x = int(input())

    if len(max_q) == len(min_q):
        heapq.heappush(max_q, -x)
    else:
        heapq.heappush(min_q, x)

    if len(min_q) != 0:
        if -max_q[0] > min_q[0]:
            a = -heapq.heappop(max_q)
            b = heapq.heappop(min_q)
            heapq.heappush(max_q, -b)
            heapq.heappush(min_q, a)

    results.append(-max_q[0])

for result in results:
    print(result)