[백준] 3273 두 수의 합

[백준] 3273 두 수의 합

• https://www.acmicpc.net/problem/3273

풀이1

• 투포인터 알고리즘

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

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

	int n;
	cin >> n;
	vector<int> vec;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}
	int x;
	cin >> x;

	int cnt = 0;
	//투포인터 알고리즘
	sort(vec.begin(), vec.end());
	int left = 0;
	int right = n - 1;
	while (left < right) {
		if (vec[left] + vec[right] > x) {
			right--;
		}	
		else if (vec[left] + vec[right] < x) {
			left++;
		}	
		else if (vec[left] + vec[right] == x) {
			right--;
			left++;
			cnt++;
		}
	}

	cout << cnt;
	return 0;
}

풀이2

• set 사용 풀이

• vec 오름차순 정렬한 후, vec[i]와 더했을 때 합이 x가 되는 수 set에 저장
  -> 이미 해당 수가 set에 존재하는 경우, 합으로 x를 만들 수 있다는 뜻이므로 cnt++

• ex. x = 13, vec = {1, 2, 3, 5, 7, 9, 10, 11, 12}

  i = 0, vec[0] = 1, needed = {12}, cnt = 0
  i = 1, vec[1] = 2, needed = {12, 11}, cnt = 0
  i = 2, vec[2] = 3, needed = {12, 11, 10}, cnt = 0
  i = 3, vec[3] = 5, needed = {12, 11, 10, 8}, cnt = 0
  i = 4, vec[4] = 7, needed = {12, 11, 10, 8, 6}, cnt = 0
  i = 5, vec[5] = 9, needed = {12, 11, 10, 8, 6, 4}, cnt = 0
  i = 6, vec[6] = 10, needed = {12, 11, 10, 8, 6, 4}, cnt = 1
  i = 7, vec[7] = 11, needed = {12, 11, 10, 8, 6, 4}, cnt = 2
  i = 8, vec[8] = 12, needed = {12, 11, 10, 8, 6, 4}, cnt = 3

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
using namespace std;

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

	int n;
	cin >> n;
	vector<int> vec;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}
	int x;
	cin >> x;

	int cnt = 0;
	set<int> needed;

	sort(vec.begin(), vec.end());
	for (int i = 0; i < n; ++i) {
		if (needed.find(vec[i]) != needed.end()) {
			cnt++;
		}
		else {
			needed.insert(abs(x - vec[i]));
		}
	}
	
	cout << cnt;
	return 0;
}