1655 가운데를 말해요

데이터의 개수가 N이기 때문에 가운데 값을 추출하는데 lgN의 시간으로 해결해야 한다. 우선순위 큐 STL은 top 값만 알 수 있고, 그 뒤의 값은 알 수가 없다. 힙 구조로 되어있기 때문에 최대, 최소값만 알 수 있게 해놓은 것 같다

 

따라서 가운데 값을 한 번에 알기 위해서는 우선순위 큐 2개를 사용하는 것이다. 하나는 최대 힙, 나머지는 최소 힙으로 구성한다. 크기는 최대 힙의 가장 큰 값 < 최소 힙의 가장 작은 값을 유지하는 구조를 가져야 한다. 짝수개의 데이터가 들어왔을 때는 가운데 값 중 작은 값을 추출해야기 때문에 반드시 최대 힙의 가장 큰 값이 테스트 케이스의 답이 된다.

 

1) 두 개의 힙 사이즈가 같다면, 최대 힙으로 넣는다

2) 두 개의 힙 사이즈가 다르다면 최소 힙으로 넣는다

 

두 개의 top을 비교해 바꿔야한다면 바꾼다. 그러고 나면 최대 힙의 top이 답이 된다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/1655.cpp