백준 [3273] - 두 수의 합 (C++)

 

 

처음 이 문제를 봤을 때는 <algorithm>라이브러리의 find함수를 이용해서 풀면 될 것이라고 생각했다.

그래서 벡터에 입력된 수를 채워넣고 

ex) x = 13, v[0] = 5이면 x - v[0]인 8을 벡터에서 찾고, 있으면 두 원소를 벡터에서 지우는 방식으로 시간을 줄이려고 했다.

 

 

 

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

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

	vector<int> v;
	int n, a, x, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		v.push_back(a);
	}
	cin >> x;
	for (int i = 0; i < n-1; i++) {
 		if (find(v.begin() + i+1, v.end(), x - v[i]) != v.end()) {
			v.erase(find(v.begin() + i + 1, v.end(), x - v[i]));
			v.erase(v.begin() + i);
			
			i -= 1;
			n -= 2;
			cnt += 1;
		}
	}

	cout << cnt;
}

하지만 이렇게 해도 결국 3%에서 시간초과가 났다.

생각해보니 find함수도 for문을 통해서 구현되었을 것이라서, 결국 이중 반복으로 O(n^2)의 시간복잡도를 가질것이라고 생각해서 for문을 한 번만 쓰고 해결할 방법을 생각했다.

 

그렇게 생각한 방법이 입력으로 서로 다른 정수가 들어오니까, 정렬 후 가장 작은 정수와 가장 큰 정수부터 비교하면 될 것이라고 생각했다.

 

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

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

	vector<int> v;
	int n, a, x, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	cin >> x;
	for (int i = 0; i < n-1; i++) {
		if (v[i] + v[n-1] == x) {
			cnt += 1;
			n -= 1;
		}
		else if (v[i] + v[n - 1] > x) {
			i -= 1;
			n -= 1;
		}
		
	}

	cout << cnt;
}

그리고 작은 정수와 큰 정수를 더해서 x보다 크면 큰 정수보다 앞 인덱스의 정수로 바꿔 합을 구하는 방식을 선택했다.

 

ex)

input)

n = 10, v = {5, 12, 7, 10, 9, 1, 2, 3, 11, 13} x = 13일 때

정렬 후 v = {1, 2, 3, 5, 7, 9, 10, 11, 12, 13}이고, 1 + 13은 14로 13보다 크므로, i와 n을 1씩 줄여 1 + 12를 비교하게 된다. 

 

작은 정수와 큰 정수의 합이 x와 같으면 cnt에 1을 더하고, n에 1을 빼주었다.

작은 정수와 큰 정수의 합이 x보다 작으면 for문에 따라 i가 더해지면 되기 때문에 별다른 처리를 해주지 않았다.

 

if문에 else구문이 빠져서 완전하지 않지만,

else{ continue; }를 추가해주면 더 깔끔한 코드가 되었을 것 같다.