[백준 1655] 가운데를 말해요(Python) 우선순위 큐 풀이 방법

[문제] www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net [풀이] 정수를 하나씩 외칠때마다 동생은 지금까지 수중에서 중간값을 말해야 한다. sol-1) 이진 탐색으로 풀었는데 시간초과 발생.. sol-2) 우선순위 큐로 접근하여 해결하였다. - 아이디어 : 중앙값 기준으로 왼쪽은 maxheap, 오른쪽은 minheap - 중간값 기준으로 왼쪽에 맥스힙(작은 수 중에 제일 큰거), 오른쪽에 민힙(큰 수 중에 제일 작은 값 ) : 수를 정렬했다고..
Algorithm/Impressive Solution 2021. 2. 17. 11:31
1