[ 백준 ] 1655 가운데를 말해요 (python)

 

 

 

 

 

 

 

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

1655번: 가운데를 말해요

 

 

 

💡 접근 방법

맨 처음엔 쉽게 생각해서 빈 리스트 arr을 만들어 값을 하나씩 append 해주고, 그때마다 sort()를 해주면서 중간값을 찾는 방법으로 구현하였다 -> 골드2 문제였고..당연히 시간 초과🙄

 

풀이 방법을 고민해봤는데 어떻게 우선순위 큐를 사용해서 이 문제를 풀어야 하는지 감이 잡히지 않았다

그래서 다른 사람들의 풀이를 참고해 문제를 풀어냈다.

 

1️⃣ 이 문제를 풀기 위해서 두개의 Heap이 필요하다.

중간값과 중간값보다 작은 값이 담길 LeftHeap

중간값보다 큰 값이 담길 RightHeap 이렇게 두가지를 만들어준다.

(* 중간값이 LeftHeap에 담겨야 하는 이유는 불린 숫자가 짝수개 일땐 중간에 있는 두 수 중 작은 값을 출력해야 하기 때문이다 -> 작은수가 LeftHeap에 들어가기 때문 )

 

이때 LeftHeap의 첫 번째로 뽑힐 값은 중간값이 되어야 하기 때문에 최대힙으로 만들어준다.

(값에 마이너스를 붙여 제일 작은값이 뽑히도록 만들어주면 된다)

 

2️⃣ 이어서 두 heap의 길이가 같다면, LeftHeap에 값을 넣어준다. LeftHeap이 중간값의 기준이 되기 때문이다.

만약 두 Heap의 길이가 같지 않다면, RightHeap에 값을 넣어준다.

 

3️⃣ 그리고 만약 -(LeftHeap의 첫번째첫 번째 값) > RightHeap의 첫 번째 값이라면, 각 값들을 뽑아 위치를 변경해준다.

왜나면 중간값 보다 작은 값이 LeftHeap에 들어와야 하는데, LeftHeap의 첫 번째 값 == 중간값인데, 이 값이 RightHeap보다 크면 중간값 보다 작은 값이 LeftHeap에 담겨야 된다는 조건에 부합하지 않기 때문이다.

 

ex) LeftHeap = [-1, -2, -7] RightHeap = [3, 8, 9] 라고 가정해볼 때, 각각의 Heap에서 heappop를 진행하면 -(-7) > 3 이 뽑히게 된다. 이때 조건에 모순되기 때문에 LeftHeap = [-1, -2, -3] RightHeap = [7, 8, 9] 로 변경해준다.

 

4️⃣ 마지막으로 3️⃣단계까지 정리해 준후, LeftHeap를 heappop해주면 중간값이 출력되게 된다.

 

 

 

 

 

 

 

🔥 문제 풀이

 

import heapq
import sys
input = sys.stdin.readline
 
n = int(input())
# leftHeap은 최대힙으로 중간값 + 중간값보다 작은 값을 넣어준다
# rightHeap은 최소힙으로 중간값 보다 큰 값을 넣어준다
leftHeap = []
rightHeap = []
 
for _ in range(n):
    num = int(input())
 
    # 순서대로 leftHeap, rightHeap 하나씩 값을 넣어준다
    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -num)
    else:
        heapq.heappush(rightHeap, num)
 
    # 만약 rightHeap의 최소값 보다 leftHeap의 최대값이 크다면
    # 중간값 보다 큰 값이 leftHeap에 있다는 뜻이므로
    # 두 값의 위치를 바꿔준다.
    if rightHeap and rightHeap[0] < -leftHeap[0]:
        leftNum = heapq.heappop(leftHeap)
        rightNum = heapq.heappop(rightHeap)
 
        heapq.heappush(leftHeap, -rightHeap)
        heapq.heappush(rightHeap, -leftNum)
 
    print(-leftHeap[0])