[Python] 백준 1655. 가운데를 말해요

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

1655번: 가운데를 말해요

접근 방법이 백준 키로거 문제와 흡사하다.

 

[Python] 백준 5397. 키로거

키로거에서는 왼쪽 / 오른쪽 커서값을 각각 stack 자료구로에 저장했다면,

여기서는 중앙값 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽에 저장한다.

 

왼쪽 값은 max_heap로, 오른쪽 값은 min_heap로 구성하고, 중앙값은 항상 max_heap의 맨 첫번째 값이 되도록 구성한다.

 

1. 왼쪽과 오른쪽 원소의 길이가 같으면, 왼쪽에 새 값을 저장한다.

2. 만약 오른쪽 heap의 값보다 왼쪽 heap의 값이 더 크면, 오른쪽과 왼쪽의 원소값을 바꿔준다.