백준 1655. 가운데를 말해요

백준 1655번 가운데를 말해요

TRYS AND INSIGHTS

• 반으로 나눠서 최대 힙, 최소 힙으로.

  • 처음 접근
  • 정리해보면,
    • 짝수(2n개) => 최대 힙(0.."n-1") / 최소 힙(n...2n-1)
    • 홀수(2n+1개) => 최대 힙(0..n-1)/ 최소 힙("n"...2n)
  • 즉, 여기서 "" 표시한 게 중간값에 해당.
    • 짝수개 중간값⇒ max_heap[0]
    • 홀수개 중간값⇒ min_heap[0]

• 원소가 하나 들어갈 때

  • 짝수였던 경우

    • 원소 < 최대 힙의 루트
      : 최대 힙 루트를 최소 힙에 넣어주고, 원소는 최대 힙으로 넣어주기

    • 최대 힙의 루트 < 원소 < 최소 힙의 루트
      : 원소는 최소 힙으로 넣어주기(원소 = 최소 힙의 루트)

    • 원소 > 최소 힙의 루트
      : 원소는 최소 힙으로 넣어주기

  • 홀수였던 경우

    • 원소 < 최대 힙의 루트
      : 원소 최대 힙으로 넣어주기

    • 최대 힙의 루트 < 원소 < 최소 힙의 루트
      : 원소 최대 힙으로 넣어주기(원소=최대 힙의 루트)

    • 원소 > 최소 힙의 루트
      : 최소 힙 루트를 최대 힙으로 넣어주기, 원소 최소 힙으로 넣어주기

• 리팩토링 못한 게 제일 아쉬움. 시간 되면 리팩토링하고 싶다..(중복코드)

[1번 시도]

런타임에러: 네임에러. 매번 print를 해줬는데 안됨.
그래서 ans 리스트에 append해서 마지막에 출력하는 방식으로 했더니 잘됨.

SOLUTION

import sys
import heapq

def main():
    N = int(sys.stdin.readline())
    left = []; right = []   # left: 최대 힙, right: 최소 힙
    right.append(int(sys.stdin.readline())) # i=0
    ans = [right[0]]
    for i in range(1, N):
        # i가 지금까지 들어온 원소의 개수 -1개
        x = int(sys.stdin.readline())
        if i%2 == 0:
            # x 들어가기 전 h는 짝수개
            if x < -1*left[0]:
                left_root = -1*heapq.heappop(left)
                heapq.heappush(right, left_root)
                heapq.heappush(left, -1*x)
            else:
                heapq.heappush(right, x)
            ans.append(right[0])
        else:
            # x 들어가기 전 h는 홀수개
            if x < right[0]:
                heapq.heappush(left, -1*x)
            else:
                right_root = heapq.heappop(right)
                heapq.heappush(left, -1*right_root)
                heapq.heappush(right, x)
            ans.append(-1*left[0])

    for a in ans:
        print(a)

main()