[ 백준 ][ 골드2 ] 1655번 - 가운데를 말해요 ( 파이썬 )

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

1655번: 가운데를 말해요

문제

---

 

코드

---

import heapq, sys
input = sys.stdin.readline
n = int(input())
maxHeap, minHeap = [],[]
mid = int(input())
print(mid)
for _ in range(1,n):
    num = int(input())
    # mid보다 작다면 maxHeap, 크다면 minHeap에 넣는다.
    heapq.heappush(maxHeap,-num) if num < mid else heapq.heappush(minHeap,num)

    # mid의 값을 길이가 더 짧은 쪽으로 넣어준다.
    heapq.heappush(maxHeap, -mid) if len(maxHeap) < len(minHeap) else heapq.heappush(minHeap, mid)

    # 두 힙의 길이가 같다면 두 힙의 첫 번째 원소들 중 작은 것을 출력한다.
    if len(maxHeap) == len(minHeap):
        mid = heapq.heappop(minHeap) if -maxHeap[0] > minHeap[0] else -heapq.heappop(maxHeap)
    # 두 힙의 길이가 다르다면 더 긴 쪽 가장 앞의 원소를 출력한다.
    else:
        mid = -heapq.heappop(maxHeap) if len(maxHeap) > len(minHeap) else heapq.heappop(minHeap)

    print(f"{mid}")

 

풀이

---

SWEA에서 한 번 경험해본 문제다.
최대힙, 최소힙을 이용해서 중간값을 찾아내는 문제로 아이디어를 떠올리고 최대힙과 최소힙을 제대로 이해했다면 어렵지 않게 해결할 수 있다.

• 최대힙과 최소힙 중 어느 힙에 값을 넣을지 결정하기 위한 mid값을 설정해야 한다.
• 맨 처음 mid의 값은 첫 번째 원소이므로 아예 처음부터 mid로 초기화시켜준다.
• mid를 기준으로 입력받는 값이 크다면 minHeap, 작다면 maxHeap에 -1을 곱해서 넣어준다.
• 여기서 헷갈리면 안되는 것은 maxHeap은 가장 큰 값을 0번 인덱스에 놓아주고 minHeap은 가장 작은 값을 0번 인덱스에 놓아준다는 것이다.
• 예를 들어, 1 5 2 순으로 입력된다면 ( maxHeap, mid, minHeap )은 순서대로 ( [-1] , 2, [5] ) 가 된다.
• 중간값을 찾기 위해 현재 가지고 있던 mid값을 두 힙 중 짧은 힙에 넣어준다.
• 여기서 부등호는 신경쓸 필요가 없다. 왜냐하면 뒤에서 길이가 같을 때 작은 것을 출력해주기 떄문이다. ( 길이가 다르다면 크기는 어차피 정렬되어 있으므로 신경쓰지 않아도 된다.)
• 두 힙의 길이가 같다면 문제의 조건대로 두 힙의 첫 번째 원소 중 작은 것을 mid로 설정하고 출력한다.
• 두 힙의 길이가 다르다면 더 긴 힙의 가장 앞 쪽 원소가 mid값이 되고 출력된다.