(2024-10-28) 3 문제 : 백준 - 2696 (중앙값 구하기)

 

중앙값이란, 정렬했을 때 중앙에 있는 값이다. 이 값을 추적하기 위해서 두 개의 우선순위 큐를 활용하였다.

하나의 큐는 기준 값보다 작거나 같은 값을 넣는 왼쪽 큐이고, 다른 하나의 큐는 기준값보다 큰 값을 넣는 오른쪽 큐이다.

왼쪽 큐는 탑이 최대값이 되도록, 오른쪽 큐는 탑이 최솟값이 되도록 하여 중앙에 있는 숫자를 확인할 수 있도록 했다.

 

첫 번째 원소를 먼저 왼쪽 큐에 넣고, 다음 원소부터 배열을 순회하며 왼쪽 큐의 top보다 작거나 같다면 왼쪽 큐에 원소를 삽입하고 그렇지 않다면 오른쪽 큐에 삽입하였다.

 

삽입 이후엔 왼쪽 큐와 오른쪽 큐의 size를 맞춰주었다. (항상 왼쪽 큐의 top이나 오른쪽 큐의 top이 중앙값이 되도록)

원소의 총 개수 (왼쪽 큐의 size + 오른쪽 큐의 size)가 짝수라면 left와 right는 size가 같아야 하고 홀수라면 두 큐의 차이는 1이어야 한다.

 

이후, 출력할 때엔 왼쪽 큐와 오른쪽 큐중 사이즈가 더 큰놈의 top을 출력해주었다.

 

이 문제의 최종보스는 출력 형식인데, 개행이나 띄어쓰기 때문인지 자꾸 틀렸다고 나와서 몇 번 고쳤더니 맞음처리되었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();
    
    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<std::vector<std::string>> Answers(NumCase);

    for(int Case = 0; Case < NumCase; Case++)
    {
        int NumSize = 0;
        std::cin >> NumSize;

        std::vector<int> Nums(NumSize);
        for (int i = 0; i < NumSize; i++)
        {
            std::cin >> Nums[i];
        }

        Answers[Case].reserve(NumSize / 2 + 1);

        std::priority_queue<int> LeftNums;
        std::priority_queue<int, std::vector<int>, std::greater<>> RightNums;

        for (int i = 0; i < NumSize; i++)
        {
            if (LeftNums.size() == 0)
            {
                LeftNums.push(Nums[i]);
            }
            else
            {
                if (LeftNums.top() >= Nums[i])
                {
                    LeftNums.push(Nums[i]);
                }
                else if (LeftNums.top() < Nums[i])
                {
                    RightNums.push(Nums[i]);
                }
            }

            if (i % 2 != 0)
            {
                if (LeftNums.size() > RightNums.size())
                {
                    RightNums.push(LeftNums.top());
                    LeftNums.pop();
                }
                else if (LeftNums.size() < RightNums.size())
                {
                    LeftNums.push(RightNums.top());
                    RightNums.pop();
                }
            }
            else
            {
                if (LeftNums.size() < RightNums.size())
                {
                    Answers[Case].push_back(std::to_string(RightNums.top()));
                }
                else
                {
                    Answers[Case].push_back(std::to_string(LeftNums.top()));
                }
            }
        }
    }

    for (int i = 0; i < Answers.size(); i++)
    {
        std::cout << Answers[i].size() << "\n";

        for (int j = 0; j < Answers[i].size(); j++)
        {
            std::cout << Answers[i][j];

            if ((j + 1) % 10 == 0 || j == Answers[i].size() - 1)
            {
                std::cout << "\n";
            }
            else
            {
                std::cout << " ";
            }
        }
    }

    return 0;
}