[구름 알고리즘 먼데이 챌린지] Week0 : 2. 카드 교환하기

문제를 읽고 번호가 작은 사람에게 작은 수의 카드가 번호가 큰 사람에게는 큰 수의 카드를 매칭 시키면 최소 불만족도를 구할 수 있을 거라고 생각하고 단순하게 오름 차순으로 정렬하여 문제를 해결하고자 했다.

하지만, 친구 관계가 맺어진 사람끼리만 카드 교환이 가능하다는 조건이 있어 조금 더 고민해 봐야했다.

 

💡내가 생각한 방법은 그룹화 하는 것이었다. 

6 7

3 4 4 1 5 6

1 3

1 6

3 6

3 5

1 5

5 6

1 2

위 예시1을 살펴보면 2번 사람의 친구는 1번 뿐이지만 1번 사람을 거치면 3,5,6 번 사람들과도 카드 교환이 가능하다.

또한, 카드 교환은 원하는 만큼 가능하기 때문에 계속 카드 교환을 하다 보면 오름 차순으로 정렬된 형태를 가질 수 있을 것이라 생각했다.

즉, DFS로 먼저 그룹화를 진행하고 그 각 그룹내에서 오름 차순 정렬된 카드로 불만족도를 계산하고자 했다. 

각각,  group1 : {1, 2, 3, 5, 6},  group2 : {4} 이 만들어지고,

각 그룹에서 카드를 정렬하여 불만족도를 계산하면

group1 {1, 2, 3, 5, 6} : [3, 4, 4, 5, 6]  -> (1-3) + (2-4) + (3-4) + (5-5) + (6-6) = 2 + 2 + 1 + 0 + 0 = 5

group2 {4] : 1 -> (4-1) = 3 

최소 불만족도 8을 구할 수 있다.

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

int n, m, u, v, cardState[200001], visited[200001], ans;
vector<int> edge[200001];

void dfs(int cur, vector<int>& group) {
	if (visited[cur]) return;
	visited[cur] = 1;
	group.push_back(cur);
	for (auto& e : edge[cur]) {
		dfs(e, group);
	}
	return;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> cardState[i];
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	vector<vector<int>> groups;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		vector<int> group;
		dfs(i, group);
		groups.push_back(group);
	}

	for (auto group : groups) {
		vector<int> list(group.size());
		for (int i = 0; i < group.size(); i++) list[i] = cardState[group[i]];
		sort(list.begin(), list.end());
		sort(group.begin(), group.end());
		for (int i = 0; i < group.size(); i++) ans += abs(group[i] - list[i]);
	}

	cout << ans;

	return 0;
}

하지만 결과는 무참히 실패...

테스트케이스 28~32, 34, 38~42, 58,59 에서 FAIL 43에서 런타임 에러까지 발생했다.

일단 시간초과가 아닌 이상 로직엔 문제가 없다고 판단하여 문제를 다시한번 천천히 읽어보았고 불만족도 값에서 발생할 수 있는 오버플로우를 고려하여 ans변수 타입을 long long으로 수정했다.

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

int n, m, u, v, cardState[200001], visited[200001];
vector<int> edge[200001];
long long ans;

void dfs(int cur, vector<int>& group) {
	if (visited[cur]) return;
	visited[cur] = 1;
	group.push_back(cur);
	for (auto& e : edge[cur]) {
		dfs(e, group);
	}
	return;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> cardState[i];
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	vector<vector<int>> groups;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		vector<int> group;
		dfs(i, group);
		groups.push_back(group);
	}

	for (auto group : groups) {
		vector<int> list(group.size());
		for (int i = 0; i < group.size(); i++) list[i] = cardState[group[i]];
		sort(list.begin(), list.end());
		sort(group.begin(), group.end());
		for (int i = 0; i < group.size(); i++) ans += abs(group[i] - list[i]);
	}

	cout << ans;

	return 0;
}