[백준] 1655번: 가운데를 말해요

문제

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

접근 방법

1. 우선순위 큐로 일정 횟수만큼 pop 한 뒤 top을 출력 -> 시간 초과
   100,000 * 50,000번 = 5,000,000,000 무조건 시간 초과

2. 최대힙과 최소힙 2개를 이용한다.

• 최대힙의 크기 = 최소힙의 크기 or 최소힙의 크기 + 1
• 최대힙의 최대 원소 <= 최소 힙의 최소 원소
  위 두 규칙을 지키면서 스왑하며 중간값을 구한다.
  참고 : https://www.crocus.co.kr/625

풀이

1번째 : 시간 초과

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

// 9:40 ~ 10:10

int N; // 1 ~ 100000

void Solve(priority_queue<int, deque<int>, greater<int>> pq)
{
    int cnt = (pq.size()+1) / 2; // 최대 50,000번 
    
    while(--cnt > 0)
    {
        pq.pop();
    }
    
    cout << pq.top() << "\n";
}

void Input()
{

    priority_queue<int, deque<int>, greater<int>> pq;

    cin >> N;

    int temp;
    for(int i=0; i<N; i++) // 100,000번
    {   
        cin >> temp;
        pq.push(temp);
        Solve(pq);
    }
}



int main()
{
    Input();
    return 0;
}

2번째

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

// 9:40 ~ 10:10

int N; // 1 ~ 100000

priority_queue<int, deque<int>, greater<int>> minHeap;
priority_queue<int, deque<int>, less<int>> maxHeap;

void FastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void Solve(int num)
{
    // 1. 최대힙의 크기는 최소 힙의 크기보다 같거나 하나 커야한다.
    if (maxHeap.empty()) maxHeap.push(num); 
    else if (minHeap.size() == maxHeap.size()) maxHeap.push(num); 
    else minHeap.push(num);

    // 2. 최대힙의 최대 원소 <= 최소힙의 최소 원소
    if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top())
    {
        int a = maxHeap.top();
        maxHeap.pop();
        int b = minHeap.top();
        minHeap.pop();

        minHeap.push(a);
        maxHeap.push(b);
    }

    cout << maxHeap.top() << "\n";

}

void Input()
{
    cin >> N;

    int num;
    for(int i=0; i<N; i++) 
    {   
        cin >> num;
        Solve(num);
    }
}



int main()
{
    FastIO();
    Input();
    return 0;
}

정리

2가지 자료구조를 동시에 이용해서 중간값을 구하는 방식을 새롭게 알게 되었다.