Boj 3273) Sum X

문제

백준 3273

방법 1

설명

우선 정렬을 함.

맨끝에 포인터를 각각 둠.

오른쪽을 줄이는데 포인터의 합이 x 보다 작아지면 왼쪽을 움직임.

왼쪽을 늘리는데 포인터의 합이 x 보다 커지면 오른쪽을 움직임.

이러면 O(n) 인데 정렬이 O(nLogN) 이라 정렬비용이 더커짐

시간 복잡도

O(nLogN)

코드

int main()
{
	int n, x;
	cin >> n;
	vector<int> as(n);
	for (int i = 0; i < n; i++)
		cin >> as[i];
	cin >> x;

	sort(as.begin(), as.end());
	
	bool move_right = true;
	auto l_i = as.begin();
	auto r_i = --as.end();
	int ans = 0;
	while (l_i != r_i)
	{
		if (*l_i + *r_i == x) ans++;
		else if (*l_i + *r_i < x == move_right) move_right = !move_right;
		//cout << *r_i << " " << *l_i << " " << ans << endl;
		move_right ? r_i-- : l_i++;
	}
	cout << ans;
}

방법 2

설명

bitset 에 값을 저장하는 느낌으로 a 마다 x-a 가 있는지 O(1) 에 찾음.

이걸 n 번 하게 됨.

시간 복잡도

O(N)

코드

int main()
{
	int n, x;
	cin >> n;
	vector<int> as(n);
	for (int i = 0; i < n; i++)
		cin >> as[i];
	cin >> x;
	vector<int> pick(x+1);

	for (auto a : as)
		if(a <= x)
			pick[a]++;
	
	int ans = 0;
	for (auto a : as)
		if(a <= x)
			ans += pick[a] == 1 && pick[x - a] == 1;
	
	cout << ans / 2;
}