백준 2470 [c++] 두 용액

처음에는 막 구현으로 풀었다. 하지만 메모리 초과가 났다.
index를 tuple(vector<pair<int, pair<int, int>>>에 저장해 진행했지만 이 방법이 마음에 들지 않았나 보다.
그래서 메모리를 줄일 것이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
//#include <math.h>

using namespace std;

bool cmp(int v, int v2) {
	return (abs(v - 0) < abs(v2 - 0));
}

int main() {
	int n;
	cin >> n;

	vector<int> v;
	vector<pair<int, pair<int, int>>> db;
	vector<int> vSum;

	for (int i = 0; i < n; i++) {
		int nTmp;
		cin >> nTmp;

		v.push_back(nTmp);
	}
	
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size() - 1; i++) {
		for (int j = i + 1; j < v.size(); j++) {
			db.push_back({ v[i] + v[j], {i, j} });
			vSum.push_back(v[i] + v[j]); 
		}
	}

	sort(vSum.begin(), vSum.end(), cmp);

	for (int i = 0; i < db.size(); i++) {
		if (db[i].first == vSum.front())
		{
			cout << v[db[i].second.first] << " " << v[db[i].second.second];
			break;
		}
	}
	

	return 0;
}


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

메모리 제한을 풀었다. 이중 for 문을 돌려서 min 최솟값을 찾고 이것을 min에다가 갱신해줬는데.
이번에는 시간초과가 났다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
//#include <math.h>

using namespace std;

bool cmp(int v, int v2) {
	return (abs(v - 0) < abs(v2 - 0));
}

int main() {
	int n;
	cin >> n;

	vector<int> v;

	int min = 987654321;
	int i_global = 0;
	int j_global = 0;

	for (int i = 0; i < n; i++) {
		int nTmp;
		cin >> nTmp;

		v.push_back(nTmp);
	}

	for (int i = 0; i < v.size() - 1; i++) {
		for (int j = i + 1; j < v.size(); j++) {
			if (min > abs(0 - (v[i] + v[j]))) {
				i_global = i;
				j_global = j;
				min = abs(0 - (v[i] + v[j]));
			}
		}
	}

	cout << v[i_global]<< " " << v[j_global];


	return 0;
}

결국에는 Two Pointer를 이용해서 풀었다.
처음에 해결했던 방식은 메모리를 너무 초과했고
두번에 해결했던 방식은 시간을 너무 잡아먹었다. 그나마 최적화를 해보려 했지만 안됐다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
//#include <math.h>

using namespace std;

int main() {
	int n;
	cin >> n;

	vector<int> v;

	int min = 987654321;

	for (int i = 0; i < n; i++) {
		int nTmp;
		cin >> nTmp;

		v.push_back(nTmp);
	}

	sort(v.begin(), v.end());

	int start = 0;
	int end = (int)v.size() - 1;

	int idx_first;
	int idx_second;

	while (start < end) {
		int sum = v[start] + v[end];

		if (min > abs(sum)) {
			min = abs(sum);
			idx_first = start;
			idx_second = end;
			if (sum == 0)
			break;
			
		}
		
		if (sum < 0)
			start++;
		else
			end--;
		
	}

	cout << v[idx_first] << " " << v[idx_second];

	return 0;
}