https://www.acmicpc.net/problem/2696
문제
어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.
예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.
출력
각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.
예제
코드
import sys,heapq
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N = int(input())
lst = []
for _ in range(N//10 + 1): # 10개씩 입력
lst += list(map(int,input().split()))
left,right = [],[]
res = []
odd = False
for i in range(N):
num = lst[i]
# 기존 두 힙큐의 길이가 같을 때 = 홀수번째 입력을 받았을 때
if len(left) == len(right):
heapq.heappush(left,(-num,num))
odd = True
else:
heapq.heappush(right,(num,num))
odd = False
# left에 항상 중앙값이 오도록 하는 과정
if right and left[0][1] > right[0][0]:
left_num = heapq.heappop(left)[1]
right_num = heapq.heappop(right)[0]
heapq.heappush(left,(-right_num,right_num))
heapq.heappush(right,(left_num,left_num))
# 홀수번째 입력인 경우 중앙값을 추가
if odd:
res.append(left[0][1])
# 중앙값 개수 출력
print(len(res))
# 10개씩 출력
while len(res) >= 10:
print(*res[:10])
res = res[10:]
if res:
print(*res)입력이 숫자 10개씩 들어온다. 즉, 10개가 넘으면 다음 줄로 넘어가므로 이를 유의해서 입력받아야 한다.
lst += list(map(int,input().split())): 10개씩 입력받아 리스트에 추가해준다.
힙 큐 두개를 사용하여 중앙값을 판별해준다.
-
left: 최대 힙으로 구현하여, 작은 값들 중 가장 큰 수를 우선으로 둔다. -
right: 최소 힙으로 구현하여, 큰 값들 중 가장 작은 수를 우선으로 둔다. -
두 힙 큐의 길이가 같다면, 왼쪽에서 우선적으로 원소를 넣어준다. 다르다면 오른쪽이 원소가 1개 부족하므로 오른쪽에 넣어준다.
-
또한 기존 두 힙큐의 길이가 같은 경우에는, 현재 입력받은 원소가 홀수 번째라는 뜻이므로
odd를True로 변경한다.
매번
left[0][1]과right[0][0]을 비교하여,left[0][1]이 더 크다면 두 힙 큐의 원소를 바꿔준다.
- 이를 통해서
left[0][1]에는 항상 지금까지 입력받은 원소들의 중앙값이 위치하게 된다.
odd가True인 경우,res에 현재 중앙값을 저장한다.
출력 또한 10개씩 해주어야 한다.
- 만약 마지막에 10개 미만의 원소들이 남아있다면, 최종적으로 출력해주며 종료한다.
느낀 점 & 배운 점
-
힙 큐 2개를 사용하여 중앙값을 구하는 것에 대해서는 이제 이해를 마친 것 같다.
-
이번 문제는 입출력도 10개씩 해주어야 하고, 홀수번째 입력인지도 파악해야해서 조금 까다로웠던 것 같다.
