시간 초과로 실패🥲
#총 개수 n
n=int(input())
data=[]
for _ in range(n):
data.append(int(input()))
data.sort()
if len(data)%2==0:
print(data[len(data)//2-1])
else:
print(data[len(data)//2])시간 초과를 해결하려다보니, 힙을 사용하려고 했다.
처음에는 힙이 최소힙을 사용하여, 인덱스 상으로 중간에 위치한 것을 중간 값으로 출력하려고 했다. 하지만 힙은 트리구조로 힙의 가장 큰 특징은 루트 노드(root node)에 항상 최소값(최소 힙의 경우) 또는 최대값(최대 힙의 경우)이 위치한다는 것만을 보장한다는 것을 모르고 풀었다.
따라서 중간 값을 구하려면 최소 힙과 최대 힙을 모두 사용해야한다는 점을 알 게 되었다!
import heapq
import sys
n = int(sys.stdin.readline())
left, right = [], [] # left는 최대 힙(작은 수들의 집합), right는 최소 힙(큰 수들의 집합)
for _ in range(n):
num = int(sys.stdin.readline())
# 최대 힙인 left에 num을 추가할 때는 num의 부호를 반대로 해서 추가. 이는 파이썬에서 기본적으로 제공하는 힙이 최소 힙이기 때문.
if len(left) == len(right):
heapq.heappush(left, -num) # left와 right의 길이가 같으면 left 힙에 새 숫자를 추가
else:
heapq.heappush(right, num) # 그렇지 않으면 right 힙에 추가
# 만약 right의 최소값이 left의 최대값(부호를 반대로 했으므로 실제로는 최소값)보다 작다면, 두 힙의 조건을 맞추기 위해 조정
if right and -left[0] > right[0]:
left_val = -heapq.heappop(left)
right_val = heapq.heappop(right)
heapq.heappush(left, -right_val)
heapq.heappush(right, left_val)
# 중앙값 출력. left와 right의 크기가 같지 않다면 left의 최대값(실제로는 중앙값)을 출력
print(-left[0])
