[백준 2831번] 댄스 파티

난이도: 골드 III

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

2831번: 댄스 파티

 

백준 2831번 문제 댄스 파티

약 3개월 전에 도전했다가 틀리고 미뤄뒀던 (...) 문제입니다.

당시에는 막 조합 생각하고 그랬던 것 같은데... 지금 풀어보니 5분만에 금방 풀리네요 ㅎㅎ

 

주어진 문제를 보면, 남자와 여자의 키가 각각 주어집니다.

이 때 키가 양수로 주어진다면 해당 사람은 본인보다 키가 큰 이성과 춤을 추고 싶은 사람이고, 키가 음수로 주어진다면 해당 사람은 본인보다 키가 작은 이성과 춤을 추고 싶은 사람입니다.

따라서 계산을 편리하게 하기 위해, 남녀, 양수/음수 총 4개의 리스트를 만듭니다.

male_pos, female_pos의 경우에는 값을 그대로 넣고, male_neg, female_neg에는 비교를 쉽게 하기 위해 값을 절댓값을 취하여 넣어줍니다.

 

그 다음, 4개의 리스트를 모두 정렬해 줍니다.

정렬 기준은 모두 오름차순 혹은 모두 내림차순으로 해야 합니다. 저는 내림차순으로 진행하였습니다.

 

pos는 자신보다 키가 큰 이성과 춤을 추고 싶은 사람, neg는 자신보다 키가 작은 이성과 춤을 추고 싶은 사람입니다.

male_pos, female_neg과 female_pos, male_neg 두 쌍에 대해 각각 아래와 같은 과정을 반복합니다.

 

1. 두 값 i, j를 0으로 초기화 합니다.
2. while(i < pos.size && j < neg.size) 동안 다음을 반복합니다.
   1. pos[i]와 neg[j]를 비교합니다. pos[i] < neg[j]인 경우, 서로 춤을 추고 싶은 사람을 만난 것입니다. 따라서 정답 값을 1 올리고, i와 j의 값을 1 올립니다.
   2. pos[i] < neg[j]가 아닌 경우, i와 j는 각각 다른 사람을 찾아봐야 합니다. i는 키가 더 큰 사람을 원하고, j는 키가 더 작은 사람을 원합니다. 리스트가 오름차순으로 정렬되어 있으므로, i에게 j보다 더 키가 큰 사람은 이미 짝이 지어졌거나 지나온 사람입니다. 반면, j는 i의 다음 순서의 사람이 i보다 키가 작으므로, j를 i+1과 비교해 보면 됩니다. 따라서 i값만 1 증가시킵니다.

loop가 종료되면, 가능한 최대의 남녀 쌍의 개수를 얻을 수 있습니다.

n은 최대 100000이므로, 총 20만번의 비교 이내에 답을 얻을 수 있습니다 (O(N) 시간 복잡도).

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, temp;
	//양수: 자신보다 키가 큰 이성과 춤을 추고 싶다.
	//음수: 자신보다 키가 작은 이성과 춤을 추고 싶다.
	vector<int> male_pos;
	vector<int> male_neg;
	vector<int> female_pos;
	vector<int> female_neg;
	cin >> n;
	for (int i = 0; i < n; i++) {
	cin >> temp;
	if (temp > 0) male_pos.push_back(temp);
	else male_neg.push_back(abs(temp));
	}
	for (int i = 0; i < n; i++) {
	cin >> temp;
	if (temp > 0) female_pos.push_back(temp);
	else female_neg.push_back(abs(temp));
	}
	sort(male_pos.begin(), male_pos.end(), greater<int>());
	sort(male_neg.begin(), male_neg.end(), greater<int>());
	sort(female_pos.begin(), female_pos.end(), greater<int>());
	sort(female_neg.begin(), female_neg.end(), greater<int>());
	int cnt = 0;
	int i = 0, j = 0;
	while (i < male_pos.size() && j < female_neg.size()) {
	if (male_pos[i] < female_neg[j]) {
	cnt++;
	i++;
	j++;
	}
	else {
	i++;
	}
	}
	i = 0; j = 0;
	while (i < female_pos.size() && j < male_neg.size()) {
	if (female_pos[i] < male_neg[j]) {
	cnt++;
	i++;
	j++;
	}
	else {
	i++;
	}
	}
	cout << cnt;
	return 0;
	}

view raw 2831_댄스 파티.cpp hosted with ❤ by GitHub

투-포인터 방식으로 어렵지 않게 풀 수 있는 문제였습니다.

이 문제를 왜 3개월 전에는 그렇게 고민하고 헤맸는지...

 

채점 결과