백준 3273번 - 두 수의 합

처음 생각한 코드는 이렇다.

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

int main()
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, temp, target;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++)
	{
		cin >> temp;
		v.at(i) = temp;
	}
	sort(v.begin(), v.end());

	cin >> target;

	int cnt = 0;

	for(int i = 0; i < n-1; i++)
	{
		for(int j = n-1; j>i; j--)
		{
			const int sum = v[i] + v[j];
			if (sum > target)
			{
				continue;
			}
			else if (sum < target)
			{
				break;
			}
			else // sum == target
			{
				cnt++;
				break;
			}			
		}
	}

	cout << cnt;

	return 0;
}

이중반복문을 활용해서 구현했다.

하지만 시간초과가 뜬다. 이중반복문이라 그런듯.

그리고 예를 들어 v[0]에서 나머지 모든 값들을 다 시도해봤는데 cnt가 안될 경우도 있는데 하는 것은 너무나 비효율적이라 생각했다.

어차피 서로 다른 양의 정수라 했으므로 v[0] + v[n-1]을 했을 때 값이 같지 않으면 이미 거기서 아웃이다.

그래서 투 포인터를 활용했다.

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

int main()
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, temp, target;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++)
	{
		cin >> temp;
		v.at(i) = temp;
	}
	sort(v.begin(), v.end());

	cin >> target;

	int cnt = 0;

	int i = 0;
	int j = n - 1;
	while(i<j)
	{
		int sum = v[i] + v[j];
		if(sum>target)
		{
			j--;
			continue;
		}
		else if(sum < target)
		{
			i++;
			continue;
		}
		else // sum == target
		{
			cnt++;
			i++;
			j--;
		}
	}

	cout << cnt;

	return 0;
}

v.push_back()을 한 것보다 단순히 v.at()을 한 것이 조금 더 메모리를 적게 잡아먹었다.