✅ priority_queue (Minheap, Maxheap)

문제

링크

풀이

1. 문제 접근

홀수가 나올때마다 이전 수들을 우선순위큐에 저장하여 중앙값을 구하기에는 M의 범위에 의해 O(9999 * 9999) 이라 불가능하다.
따라서 수열을 순서대로 돌면서 그때그때 바로 중앙값을 꺼내올 수 있게 해야한다.

2. 자료구조 선택과 그 이유

우선순위 큐를 하나만 사용하면 위에서 말한대로 불가능하다.

하지만 우선순위 큐를 두개 사용하여 나눠 담으면 중앙값을 바로 꺼내올 수 있다.

3. 문제 해결 로직 (풀이법)

짝수번째일 경우에는
이전에 나온 숫자들을 다시 꺼내 새로 넣을 숫자의 크기를 비교할 필요 없이
두개의 우선순위 큐의 사이즈만 통일 시켜주면된다.

홀수번째일 경우에는
maxheap과 minheap가 사이즈가 같으므로 num이 maxheap.top보다 크면 minheap에, maxheap.top보다 작으면 maxheap에 저장한다.

의사코드

cin >> T
while(T--){
	cin >> M
    priority_queue<int> maxheap
    priority_queue<int, greater> minheap
    
    cin >> num
    maxheap.push(num)
    vector.push_back(num)
    
    for(i : 2 ~ M){
    	cin >> num
        if(i%2 == 1){ // 홀수일때
        	if(maxheap.top < num) minheap.push(num)
            else maxheap.push(num)
            
            if(maxheap.size > minheap.size) vector.push_back(maxheap.top)
            else vector.push_back(minheap.top)
        }
        else{ // 짝수일때
        	if(maxheap.size > minheap.size) minheap.push(num)
            else maxheap.push(num)
        }
    }
}

cout << M/2+1
for(i : 0 ~ vector.size - 1){
	if(i%10 == 0) cout << "\n
    cout << vector[i]
}

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

중앙값을 구하는데 우선순위 큐를 2개 사용(Minheap, Maxheap)할 수 있다는 것을 처음 적용해본 문제