2022.02.16 [백준] (python 파이썬) 가운데를 말해요

 

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

1655번: 가운데를 말해요

 

---

풀이

이 문제를 풀기 위해서는 2개의 heap이 필요하다.

leftheap과 rightheap을 만들었다. leftheap을 왼쪽, rightheap을 오른쪽이라고 보자.

그럼 중간값보다 작은건 왼쪽, 큰건 오른쪽에 저장할 것이다.

이 때 두값을 비교하기 위해 왼쪽에는 (-num,num)으로 저장해준다.

그러면 왼쪽은 최대값이 루트노드가 될것이다. 

 

이코드를 작성할 때 3가지 조건을 주었다.

1. 왼쪽 오른쪽 힙의 길이가 같으면 왼쪽에 push해준다.

2. 길이가 다르면 왼쪽이 길기 때문에 오른쪽에 push해준다.

3. 입력받은 숫자를 push해준 뒤, 왼쪽의 루트노드값과 오른쪽의 루트노드값을 비교한다.

   만약 왼쪽의 값이 크면 각 값을 바꿔준다.(이유는 왼쪽은 중간값보다 작은것을 넣어야 하는데 

   오른쪽 값보다 크면 중간값보다 큰값을 넣은것이 되기 때문이다. 또한 입력받은 값이 짝수면

   두 중간값 중 작은 값을 출력해야 하기 때문이다.)

 

이 후 왼쪽의 루트노드값이 항상 중간값이 되므로 왼쪽 루트노드값을 ans배열에 담아준다.

 

왼쪽값에서 숫자를 뺄때는 최대값을 루트노드로 올리기 위해(-num, num)으로 저장했기 때문에 

leftheap[i][1]이 입력받은 숫자가 된다. 

import heapq
import sys
 
input=sys.stdin.readline
 
n=int(input())
 
leftheap=[]
rightheap=[]
ans=[]
for i in range(n):
    num=int(input())
    if len(leftheap)==len(rightheap):
        heapq.heappush(leftheap,(-num,num))
    else:
        heapq.heappush(rightheap, (num,num))
    if rightheap and leftheap[0][1]>rightheap[0][0]:
        temp1=heapq.heappop(leftheap)[1]
        temp2=heapq.heappop(rightheap)[0]
        heapq.heappush(leftheap,(-temp2,temp2))
        heapq.heappush(rightheap,(temp1,temp1))
    ans.append(leftheap[0][1])
for i in ans:
    print(i)