[백준 2831] 댄스 파티

문제

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

 

알고리즘

sorting

 

풀이

자신이 선호하는 조건에 따라 매칭할 수 있는 최대 남녀쌍을 묻는 문제입니다.

 

만일 키가 양수라면 이성의 키의 값이 음수인 사람과 매칭해야하고 반대로 키가 음수라면 이성의 키가 양수인 사람을 매칭해야합니다. 두 경우 모두 동일하므로 남성의 키가 양수, 여성의 키가 음수인 경우만 보겠습니다.

 

남성의 키가 양수인 배열과 여성의 키가 음수인 배열을 정렬을 합니다. 배열의 앞에서부터 매칭을 시작합니다. 만일 조건이 만족한다면 다음 남녀쌍이 조건을 만족하는지 검사하면 됩니다. 단 조건을 만족하지 않는다면, 현재 매칭되지 않은 남성은 그대로 두고 여성은 다음 여성과 매칭되는지 확인해야합니다. 조건을 만족하지 않는다는 것은 여성의 키가 더 작고 남성의 키가 더 큰 상황인데 키가 정렬된 상태이므로 다음 남성과 현재 여성을 매칭하면 매칭될 수 가 없기 때문입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, ans;
vector<int> mh, ml, wh, wl;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        int x;
        cin >> x;
        if (x > 0) mh.emplace_back(x);
        else
            ml.emplace_back(-x);
    }
    rep(i, N) {
        int x;
        cin >> x;
        if (x > 0) wh.emplace_back(x);
        else
            wl.emplace_back(-x);
    }
    sort(mh.begin(), mh.end());
    sort(ml.begin(), ml.end());
    sort(wh.begin(), wh.end());
    sort(wl.begin(), wl.end());

    int pa = 0;
    int pb = 0;
    while (pa < mh.size() && pb < wl.size()) {
        if (mh[pa] < wl[pb]) {
            ans += 1;
            pa++;
            pb++;
        } else
            ++pb;
    }

    pa = 0;
    pb = 0;
    while (pa < ml.size() && pb < wh.size()) {
        if (ml[pa] > wh[pb]) {
            ans += 1;
            pa++;
            pb++;
        } else
            ++pa;
    }
    cout << ans;
    return 0;
}