힙1 [백준 1655] 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 중간값 찾기 알고리즘을 사용한다. maxHeap과 minHeap이 필요해서 우선순위큐를 사용한다. 두 힙은 다음과 같은 규칙을 따른다. 1. maxHeap은 minHeap의 크기와 같거나 1만큼 크다. 2. maxHeap의 탑은 minHeap의 탑보다 작거나 같다. 만약 이를 만족시키지 못하면 둘을 바꾼다. 이렇게 하면 maxHeap의 탑이 항상 중간값임을 알 수 있다. 신기방기.. 예제에 적용.. 2021. 1. 14. 이전 1 다음