가운데를 말해요

import heapq
import sys

def BOJ1655():
  n = int(sys.stdin.readline())
  leftheap = []
  rightheap = []
  
  for _ in range(n) :
    input_num = int(sys.stdin.readline())

    if len(leftheap) == len(rightheap) :
      heapq.heappush(leftheap, (-input_num, input_num))
    else :
      heapq.heappush(rightheap, (input_num, input_num))
    
    if rightheap and leftheap[0][1] > rightheap[0][1] :
      leftmin = heapq.heappop(leftheap)[1]
      rightmin = heapq.heappop(rightheap)[0]
      heapq.heappush(leftheap, (-rightmin, rightmin))
      heapq.heappush(rightheap, (leftmin, leftmin))

    print(leftheap[0][1])

BOJ1655()

 

접근 방법 :

1. 시간제한이 심상치않게 짧은것을 확인할 수 있다.(python의 경우 0.6초의 제한이다) 문제에서 요구하는 것 자체는 간단하다. 중앙값을 출력해주면 된다.

2. 테스트 삼아 배열을 매번 정렬을 하고 배열의 중앙값을 출력해 주었었지만 역시나 시간 초과다. 

3. 두개의 힙을 이용하여서 풀었다.
(상단의 원래 하나였던 배열을 하단의 두개의 배열로 쪼갰다고 보시면 됩니다. 이러면 왼쪽 힙은 내림차순 정렬, 오른쪽 힙은 오름차순 정렬을 해야겠다는 그림이 보이실겁니다.)

4. 힙을 선택한 이유는 다음과 같습니다. 값을 넣어줄때마다 sort를 이용해주면 시간은 당연히 초과할것으로 판단하여 heapq를 이용하기로 하였습니다.

5. 값을 입력받으면 중앙값의 위치를 유지시켜주기 위해 두 힙의 길이를 비교하여 두 힙간의 길이 차이가 최대 1이 되게 유지하여 줍니다.

6. 전체 과정을 아래와 같이 도표로 나타내었습니다.

 

7. 값을 힙에 넣어준후 각 힙의 끝 값들의 대소 비교를 통해 알맞은 위치에 값을 위치 시켜줍니다.

8. 힙의 인덱스를 통한 접근으로 원하는 답을 가져올 수 있음을 확인하였습니다.

 

출처: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요