백준 1655번 가운데를 말해요

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

사용한 알고리즘: priority_queue(우선순위 큐)


 입력으로 수들이 주어지고, 그 수들의 중간값을 말해주는 문제입니다. sort의 시간복잡도가 O(nlogn) 이므로, 10^5개를 한번만 sort 한다고 쳐도 대략 (10^5)*(log2(10^5)) = 17*10^5 정도이니, 입력이 주어질 때마다 sort를 하게되면 1 + 2*1 + ..... + 17*10^5 가 되므로,
당연히 터지게 됩니다. 따라서 pq 2개를 써서 풀면 되는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) 중간값을 MID 라 하면, MID 를 기준으로 MID보다 작은 값들을 모아, 가장 큰 값이 위로 오게 하는 priority_queue<int, vector<int>, less<int>> MinQ 와 MID를 기준으로 MID보다 큰 값들을 모아, 가장 작은 값이 위로 오게 하는 priority_queue<int, vector<int>, greater<int>> MaxQ 를 각각 만들어 줍니다.

(2) 처음 입력값을 MID 값으로 합니다. 이후 들어오는 수를 MID보다 작으면 MinQ, 크면 MaxQ에 넣어줍니다.

(3) MID 가 중간값인지 확인해야합니다. 입력된 수들의 개수가 홀수개면 MinQ의 개수와 MaxQ의 개수가 같아야 합니다. 다르다면 같게 만들어 줍니다. 예를들어 MinQ (개수 4), MID , MaxQ (개수 2) 이면, MID 를 MaxQ에 넣고, MinQ의 top 값을 빼서 MID 값으로 해줍니다. 이러면 MinQ (개수 3), MID, MaxQ (개수 3) 이 되어 MID 값이 됩니다. 만약 입력된 수들의 개수가 짝수개면 MinQ, MaxQ 개수 차가 1개가 되는데, 개수가 많은쪽의 top값과 MID 값을 비교하여 둘중 작은 값을 출력해주면 됩니다.