BOJ [중앙값 구하기]

문제

2022-03-29

문제 보기

배열이 있고 배열을 index 순으로 탐색하는데 홀수번 index마다 0~index 까지의

중앙값을 print 하라는 문제이다.

풀이

내 풀이

나는 새 배열을 만들어서 숫자를 넣을때마다 이분탐색으로 숫자를 넣었다.

그래서 insert 모듈을 쓰므로 O(N)이 걸리고 이분탐색에서 O(logN)이 걸렸다.

from bisect import bisect_left, bisect_right

n = int(input())


for _ in range(n):
  
  m = int(input())
  arr = [] 
  while len(arr) < m:
    arr += list(map(int,input().split()))
  sorted_arr = [arr[0]]
  mid = [arr[0]]
  for i in range(1,len(arr)):
    temp_index = bisect_left(sorted_arr,arr[i])
    sorted_arr.insert(temp_index,arr[i])
    if i%2 ==0 :
      mid.append(sorted_arr[i//2])
  print(len(mid))
  for num in mid:
    print(num,end=' ')

정석 풀이

답지 풀이는 max_heap, min_heap 두개를 썼는데 가운데 중앙값을 기준으로 중앙값보다

작으면 max_heap에 추가하고 크면 min_heap에 추가한다.

적당히 조절해서 홀수때마다 각 heap에서 pop해주면 된다.

이 풀이는 O(logN)이 걸리는데 왜 내 풀이가 작동시간이 더 짧은지 모르겠다...

import heapq 

n = int(input())

for _ in range(n):
  
  m = int(input())
  arr = []

  
  
  while len(arr)<m:
    arr += list(map(int,input().split()))
  
  small_max = []
  big_min = []
  mid = arr[0]
  answer = [arr[0]]
  
  for i in range(1,m):
    if i%2 == 0:
      if arr[i] > -small_max[0]:
        heapq.heappush(big_min,arr[i])
        mid = heapq.heappop(big_min)
        answer.append(mid)
      else:
        heapq.heappush(small_max,-arr[i])
        mid = -heapq.heappop(small_max)
        answer.append(mid)
    else:
      if arr[i]>= mid:
        heapq.heappush(big_min,arr[i])
        heapq.heappush(small_max,-mid)
      else:
        heapq.heappush(small_max,-arr[i])
        heapq.heappush(big_min,mid)

  print(len(answer))
  
  for i in answer:
    print(i,end = ' ')