백준 - 2831 댄스 파티

문제

자신보다 키가 크거나 작거나로 선호하는 이성 유형이 주어질 때
서로 원하는 유형을 만족하는 춤 출 쌍을 최대 몇 쌍 만들 수 있을까?

생각

키가 작은 여자랑 만나고 싶은 남자, 키가 큰 남자랑 만나고 싶은 여자
키가 큰 여자랑 만나고 싶은 남자, 키가 작은 남자랑 만나고 싶은 여자
를 보고 매칭해주자!

키를 오름차순으로 정렬하고

아닌 경우엔 나보다 작은 사람 찾는 벡터 index++

1. 벡터 사용

키를 오름차순 정렬하고 index 늘려가며 접근하는 방법을 생각했다

서로 만족되면 result++,
아닌 경우에는 '나보다 작은 사람 찾아요~' 벡터 index++
(자신보다 작은 사람을 찾는데, 가능한 최대한 작은 사람보다 더 작으면 매칭 안 됌)

int j = 0;
if (pw.size() > 0) {
    for (int i = 0; i < nm.size(); i++) { //나보다 작은 사람 찾아요~ 벡터를 돌면서
        if (nm[i] > pw[j]) { 
            result++;
            if (++j >= pw.size()) { // 매칭되면 나보다 큰 사람 찾아요~ 벡터 index++!
                break; //이거 꼭 해줘야함. 안 하면 n^2으로 시간초과!
            }
        }
    }
}

while(1) 해서 두 벡터 돌 수도 있긴한데
하나는 for문으로 돌려서 계속 ++해주고, 하나는 매칭되면 ++해주면서
하나라도 다 쓰면 탈출이라는 게 의미상 이해하기 좋아보여서 이렇게 구현했다

2. 우선순위 큐 사용

구글링해보니까 우선순위 큐를 써서 많이들 구현하길래 나도 해봄
확실히 index 접근말구 empty() 같은거 쓰면되니까 런타임 에러도 안 나고, 이해도 쉽고 좋다

신기한건 내 코드에서 벡터보다 시간이 더 걸리더라
넣을때 이쁘게 넣고 보고 꺼내고 보고 꺼내고 그래서 그런가?

구현 아이디어는 똑같다!!

while (1) {
    if (pw.empty() || nm.empty()) {
        break; // 둘 중 하나라도 빌 때까지 반복문 돌면서 매칭
    }
    int tpw = pw.top();
    int tnm = nm.top();
    nm.pop(); // 나보다 작은 사람 찾아요~ 는 계속 꺼내면서 보자!
    if (tnm > tpw) {
        result++; 
        pw.pop(); // 매칭되면 나보다 큰 사람 찾아요~ 사람 꺼내!
    }
}

코드

1. 벡터 사용

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

vector<int> pm, nm, pw, nw;

int main() {
	int n, tmp, result = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0) {
			pm.push_back(tmp);
		}
		else {
			nm.push_back(-1 * tmp);
		}
	}

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0) {
			pw.push_back(tmp);
		}
		else {
			nw.push_back(-1 * tmp);
		}
	}

	sort(pm.begin(), pm.end());
	sort(nm.begin(), nm.end());
	sort(pw.begin(), pw.end());
	sort(nw.begin(), nw.end());

	//음수 남자들과 양수 여자들
	int j = 0;
	if (pw.size() > 0) {
		for (int i = 0; i < nm.size(); i++) {
			if (nm[i] > pw[j]) {
				result++;
				if (++j >= pw.size()) {
					break;
				}
			}
		}
	}

	//양수 남자들과 음수 여자들
	if (pm.size() > 0) {
		j = 0;
		for (int i = 0; i < nw.size(); i++) {
			if (nw[i] > pm[j]) {
				result++;
				if (++j >= pm.size()) {
					break;
				}
			}
		}
	}

	cout << result;

	return 0;
}

2. 우선순위 큐 사용

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

priority_queue<int, vector<int>, greater<int>> pm, nm, pw, nw;

int main() {
	int n, tmp, result = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0) {
			pm.push(tmp);
		}
		else {
			nm.push(-1 * tmp);
		}
	}

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0) {
			pw.push(tmp);
		}
		else {
			nw.push(-1 * tmp);
		}
	}

	//음수 남자들과 양수 여자들
	while (1) {
		if (pw.empty() || nm.empty()) {
			break;
		}
		int tpw = pw.top();
		int tnm = nm.top();
		nm.pop();
		if (tnm > tpw) {
			result++;
			pw.pop();
		}
	}
	
	//양수 남자들과 음수 여자들
	while (1) {
		if (pm.empty() || nw.empty()) {
			break;
		}
		int tpm = pm.top();
		int tnw = nw.top();
		nw.pop();
		if (tnw > tpm) {
			result++;
			pm.pop();
		}
	}
	
	cout << result;

	return 0;
}