[백준] 3273번 두 수의 합 (배열, 포인터 c++)

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

3273번: 두 수의 합

 

두 가지 방법으로 풀 수 있다.

하나는 원소 체크(기록)을 해서 배열의 원소 a에 대해서 x-a가 배열에 있는 지 체크하는 법

또 하나는 정렬 후 투포인터를 이용하는 법.

 

 

1. 기록

#include <iostream>
using namespace std;

int num[100001];
int cnt[2000001];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,tmp,x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		num[i]=tmp;
		cnt[tmp] = 1;
	}
	cin >> x;
	int sum = 0;
	for (int i = 0; i < n; i++) {
    	// x-num[i]가 음수면 런타임에러나므로 조심
		if (x-num[i]>=0 && cnt[x - num[i]] != 0 && x-num[i]>num[i]) {//i<j조건도 넣어준다.
			sum += 1;
		}
	}
	cout << sum;
	return 0;
}

 

2. 투포인터 방법

 

정렬 후 가장 작은 수(left)와 큰수(right)를 더해가면서 가능한 쌍의 개수를 본다.

 

#include <iostream>
using namespace std;

int num[100001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,tmp,x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	cin >> x;
	sort(num, num + n);
	int sum = 0;
	int left = 0, right = n - 1;
	while (left < right) {
		if (num[left] + num[right] == x) {
			sum += 1;
			left += 1;
			right -= 1;
		}
		else if (num[left] + num[right] > x) {
			right -= 1;
		}
		else {
			left += 1;
		}
	}
	cout << sum;
	
	return 0;
}