[G4] 백준 2831번 댄스 파티 C++ 정렬, 투 포인터

리뷰

 

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

원하는 조건에 맞는 쌍을 최대한 많이 매칭시키기 위한 문제

 

 

전역 변수

• n : 남자 여자 쌍의 수를 저장할 변수

 

함수

1. matching

int matching(const vector<int>& ws, const vector<int>& wt) {
	int match = 0;
	int s_idx = 0;
	int t_idx = 0;
	int ss = ws.size();
	int ts = wt.size();
	while (s_idx < ss && t_idx < ts) {
		int mh = ws[s_idx];
		int wh = wt[t_idx];

		if (wh < mh) {
			++match;
			++s_idx;
			++t_idx;
		}
		else ++s_idx;
	}
	return match;
}

 

매칭될 수 있는 최대 쌍을 찾아 매칭된 쌍의 수를 반환하는 함수

 

 

문제풀이

1. n값을 입력 받고, 정수형 벡터 sm, tm, sw, tw를 초기화한다.
2. n명의 남자의 키를 입력 받아 음수일 경우 양수로 변환하여 sm에, 양수일 경우 tm에 추가한다.
3. n명의 여자의 키를 입력 받아 음수일 경우 양수로 변환하여 sw에, 양수일 경우 tw에 추가한다.
4. sort함수를 통해 sm, tm, sw, tw벡터를 모두 오름차순으로 정렬한다.
5. matching함수에 sm, tw와 sw, tm을 전달하여 반환 받은 정수의 합을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. matching함수는 작은 키를 원하는 그룹을 첫번째 매개변수, 큰 키를 원하는 그룹을 두번째 매개변수로 전달한다.
2. 모든 키가 오름차순으로 정렬되어 있을때 두 포인터를 각 벡터의 0번 인덱스부터 출발한다.
3. 조건에 부합하면 matching을 증가, 두개의 포인터를 모두 증가, 아니라면 작은 키를 원하는 벡터의 포인터만 증가시킨다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;

int matching(const vector<int>& ws, const vector<int>& wt) {
	int match = 0;
	int s_idx = 0;
	int t_idx = 0;
	int ss = ws.size();
	int ts = wt.size();
	while (s_idx < ss && t_idx < ts) {
		int mh = ws[s_idx];
		int wh = wt[t_idx];

		if (wh < mh) {
			++match;
			++s_idx;
			++t_idx;
		}
		else ++s_idx;
	}
	return match;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	vector<int> sm, tm, sw, tw;
	for (int i = 0; i < n; ++i) {
		int h; cin >> h;
		if (h < 0) sm.push_back(-h);
		else tm.push_back(h);
	}

	for (int i = 0; i < n; ++i) {
		int h; cin >> h;
		if (h < 0) sw.push_back(-h);
		else tw.push_back(h);
	}

	sort(sm.begin(), sm.end());
	sort(tm.begin(), tm.end());
	sort(sw.begin(), sw.end());
	sort(tw.begin(), tw.end());

	cout << matching(sm, tw) + matching(sw, tm);
}