[구름 알고리즘 먼데이 챌린지] Week3 : 1. 0커플

구름이의 실수로 인해 소개팅을 받지 못하는 커플은 단 한쌍이므로 한쌍을 제외한 모든 사람은 자신의 점수 n에 반대 되는 -n점의 사람을 찾을 수 있다.

 

처음엔 단순하게 이중 for문으로 0번째 사람부터 n-1번째 사람까지 탐색하며 각자의 짝을 찾고자 하였다. 

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

int n;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	vector<int> people(n);
	vector<int> check(n, 0);
	for (int i = 0; i < n; i++) cin >> people[i];
	for (int i = 0; i < n -1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (people[i] + people[j] == 0) {
				check[i] = check[j] = 1;
				break;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (!check[i]) {
			ans += people[i];
			flag++;
		}
	}
	cout << ans;
}

하지만 마지막 15번 테스트 케이스에서 타임아웃이 발생하였다.

먼저, 로직은 그대로 사용하고 최적의 탐색을 위해 적절히 break와 continue 조건을 걸어 보았다.

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

int n;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	vector<int> people(n);
	vector<int> check(n, 0);
	for (int i = 0; i < n; i++) cin >> people[i];
	for (int i = 0; i < n -1; i++) {
		if (check[i]) continue;
		for (int j = i + 1; j < n; j++) {
			if (check[j]) continue;
			if (people[i] + people[j] == 0) {
				check[i] = check[j] = 1;
				break;
			}
		}
	}
	int ans = 0, flag = 0;
	for (int i = 0; i < n; i++) {
		if (flag == 2) break;
		if (!check[i]) {
			ans += people[i];
			flag++;
		}
	}
	cout << ans;
}

여전히 15번 테케에서 타임아웃이 발생하였고 O(n^2)의 시간복잡도로는 문제를 해결할 수 없다고 판단하였다.

 

내가 찾은 해결법은 아래와 같다.

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

int n, a, ans;
int check[200001];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		check[(int)abs(a)] += a;
	}
	for (int i = 1; i <= 200000; i++) if (check[i] != 0) ans += check[i];
	cout << ans;
}

먼저, 문제에 입력받을 수 있는 최대 점수가 200000이므로 200001크기의 check배열을 생성한다.

이후, 점수 a를 입력받으면 check[ |a| ]에 해당 점수를 더해준다.

이렇게 해주면 예를들어, 입력 받은 점수들 중 10과 -10을 모두 입력 받았다면 check[10]의 값은 0이 될 것이고

그 외, 자신의 쌍을 입력받지 못한 수의 경우 예시1의 4와 -5의 경우 check[4]에는  4, check[5]에는 -5 저장 되어 있을 것이다. 따라서, n개의 수를 입력 받은 후 200000까지 check배열을 탐색하며 0이 아닌 값을 찾아 ans에 더해주면 되면 소개팅을 진행하지 못한 두 사람의 점수를 합한 값을 구할 수 있게 된다.

 

OMG!!😱

사실 위에 내가 생각한 풀이법도 좋은 아이디어라고 생각하고 있었다.

하지만, 해설을 보고 경악을 금치 못했다. 소개팅을 정상적으로 진행한 사람들의 점수의 합은 항상 0이기 때문에 그저 입력 받는 대로 더해주면 결국 소개팅을 진행하지 못한 사람들의 점수의 합이 도출되는 것이었다...

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, ans = 0;
    cin >> N;
    vector<int> S(N);
    for (int& n : S) cin >> n;
    cout << accumulate(S.begin(), S.end(), 0);
    return 0;
}

아직 갈 길이 멀다 ㅜㅜ