백준 2831번 댄스 파티

문제 링크입니다: https://www.acmicpc.net/problem/2831

N이 최대 100,000이기 때문에 O(NlogN)으로 풀어야하는 문제였습니다.

저는 우선순위 큐를 이용해 풀었습니다.

알고리즘은 아래와 같습니다.

1. 음수로 주어진 남성과 양수로 주어진 남성, 음수로 주어진 여성과 양수로 주어진 여성을 각각 다른 최소 우선순위 큐에 넣었습니다.

2. 1번을 완료하고 음수로 주어진 남성과 양수로 주어진 여성을 그리고 양수로 주어진 남성과 음수로 주어진 여성을 짝을 맺게 했습니다.

3. 2번의 전자 같은 경우 현재 남성과 짝을 맺을 수 있을 때까지 여성만 pop을 했고 짝이 맺어지면 그제서야 남성도 pop을 했습니다.(그리디하게 접근)

4. 2번의 후자 같은 경우 현재 여성과 짝을 맺을 수 있을 때까지 남성만 pop을 했고 짝이 맺어지면 그제서야 여성도 pop을 했습니다.(그리디하게 접근)

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <functional>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        priority_queue<int, vector<int>, greater<int>> posMale, posFemale, negMale, negFemale;

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

 

                 if (num < 0)

                         negMale.push(abs(num));

                 else

                         posMale.push(num);

        }

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

 

                 if (num < 0)

                         negFemale.push(abs(num));

                 else

                         posFemale.push(num);

        }

       

        int result = 0;

        while (1)

        {

                 if (posMale.empty() || negFemale.empty())

                         break;

 

                 int male = posMale.top();

                 int female = negFemale.top();

                 negFemale.pop();

 

                 if (male < female)

                 {

                         result++;

                         posMale.pop();

                 }

        }

        while (1)

        {

                 if (negMale.empty() || posFemale.empty())

                         break;

 

                 int male = negMale.top();

                 negMale.pop();

                 int female = posFemale.top();

 

                 if (male > female)

                 {

                         result++;

                         posFemale.pop();

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~