[Python Algorithm] 가운데를 말해요 BOJ #1655

문제

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

1655번: 가운데를 말해요

 

내 문제 풀이

import sys
import heapq

n = int(sys.stdin.readline().strip())
left = []
right = []

for _ in range(n):
    now = int(sys.stdin.readline().strip())

    if len(left) == len(right):
        heapq.heappush(left, -now)
    else:
        heapq.heappush(right, now)

    if right and right[0] < -left[0]:
        leftNum = heapq.heappop(left)
        rightNum = heapq.heappop(right)

        heapq.heappush(left, -rightNum)
        heapq.heappush(right, -leftNum)

    print(-left[0])

👉 힙 문제

• 중간 값을 기준으로 작은 값은 left 리스트에, 큰 값은 right 리스트에 저장해주었다.
  최소 힙의 경우 루트 노드에 가장 작은 값을 저장하고, 최대 힙의 경우 가장 큰 값을 저장하기 때문에
  left 리스트는 최소 힙으로, right 리스트는 최대 힙으로 만들어서 루트 노드를 통해 크고 작음을 비교했다.
  (처음에는 힙 정렬을 이용했지만, 생각해보니 굳이 모든 수를 비교할 필요가 없고
  중간 값을 기준으로 큰 값과 작은 값만 비교해주면 되었기 때문에 위와 같은 방법을 사용했다.)
• left와 right의 길이가 같을 경우 현재 입력되는 값을 포함하여 홀수개의 수가 입력되었다는 뜻이므로
  left 리스트에 값을 heappush 했고, 그 외의 경우 right 리스트에 값을 heappush 했다.
• 그리고 혹시 right의 루트 노드 값이 left의 루트 노드 값보다 더 작을 경우,
  중간 값보다 작은 값이 right에 들어갔다는 뜻이므로 두 수를 교환해주었다.
• 연산이 끝나면 left 리스트의 루트 노드 값을 출력해주었다.

 

💡 피드백

• 처음엔 힙 정렬이라고 생각해서 풀었는데, 시간 초과였다.
  알고보니 굳이 다 정렬할 필요가 없고, 중간 값을 기준으로 더 큰 값과 작은 값만 비교해주면 되는 문제였다.
• 힙의 개념을 잘 알아야 하고, 최대 힙과 최소 힙을 만들 줄 알면 되는 문제같다.
  나는 잘 몰라서 공부하면서 풀었고,,! 이제 힙을 좀 사용할줄 알게 된 것 같다.