블로그

골드 Ⅳ (우선순위 큐로 푼다는 가정하에 체감은 골드 2~3 정도이다) 난 이걸 우선순위 큐로 풀었는데 (이름도 우선순위 큐잖아...) multiset을 이용하면 비교적 간단히 풀린다고 한다 이름이 우선순위 큐이기도 하고, 백준에 가운데를 말해요 라는 재미있는 문제가 있는데, 보자마자 그런 max heap / min heap 응용류일거라고 생각이 들어서 우선순위 큐로 접근을 했던 것 같다 문제 접근 방법은, 백만개의 쿼리에 대해서 최대 / 최소 값을 바로바로 얻어낼 수 있는 방법은 최대 힙 / 최소 힙을 이용해 insert 로 들어오는 쿼리 값들을 모두 최대 힙 / 최소 힙 에 넣어주면 최대 / 최소값을 바로바로 알아낼 수 있다. 또한, 최대 / 최소 값을 빼 내는 D 쿼리의 경우 최대 힙에서 최대값을 ..