https://www.acmicpc.net/problem/1655
문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
출력
한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
풀이
각각의 입력이 주어질 때마다 현재까지 입력된 숫자들의 중간값을 계속해서 출력해주어야 한다. 입력할 때마다 정렬하면 시간이 오래걸리므로 우선순위 큐를 이용하는게 적합하다고 생각하였다.
중간값을 출력해야 하므로 힙을 하나만 사용할 경우 중간값이 나올 때까지 pop해준 후 다시 push 해주어야 한다. 따라서 최소힙과 최대힙 두개를 적절히 이용해야 한다고 생각했다.
중간값은 짝수일 경우 무조건 작은 쪽을 출력한다. 따라서 중간값 두개를 바로 비교할 수 있게 중간값을 기준으로 왼쪽에 최대힙, 오른쪽에 최소힙을 사용하고 길이를 저장하는 변수를 이용해 계속해서 길이를 일정하게 유지해주면 된다.
입력과 출력시 무조건 왼쪽힙을 사용한다. 왼쪽힙의 길이-오른쪽힙의 길이가 1이하가 되게 유지하면 홀수와 짝수일 때 모두 왼쪽힙의 값을 사용하게 된다.
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
n = int(input())
minq, maxq = [],[]
minl, maxl = 0,0
for i in range(n):
num = int(input())
heappush(minq, -num)
minl += 1
if minl - maxl > 1:
heappush(maxq, -heappop(minq))
minl -= 1
maxl += 1
print(-minq[0])반례
라고 생각했었는데 반례가 존재했다.
4
2
3
4
1입력값의 크기를 고려하지 않고 무작정 push해서 틀렸었는데, 왼쪽의 최대힙과 오른쪽의 최소힙의 크기를 비교하고, 왼쪽의 값이 더크면 오른쪽의 값과 스왑하도록 조건문을 추가해 해결하였다.
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
n = int(input())
minq, maxq = [],[]
minl, maxl = 0,0
for i in range(n):
num = int(input())
heappush(minq, -num)
minl += 1
if minl - maxl > 1:
heappush(maxq, -heappop(minq))
minl -= 1
maxl += 1
elif minq and maxq and -minq[0] > maxq[0]:
m1 = -heappop(minq)
m2 = heappop(maxq)
heappush(minq, -m2)
heappush(maxq, m1)
print(-minq[0])
