[BOJ/C++] 1253 좋다 : Two Pointer

문제

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

풀이

1. 처음 접근
1 2 3 4 5 6 7 8 9 10이 있을 때, 이 수를 두 개의 합으로 나타낼 수 있다면
target=3인 경우, 반복문 돌면서 j=1일 때, 3-1=2가 존재하는지 확인하는 방법 사용
이 때, 2는 target index와도 다르고, j index와도 달라야한다.

But. 수가 0 0 0 이런 식으로 있을 때, index를 찾는데 뒤에 해당 수가 존재해도 find 함수는 앞에서부터 탐색하므로 오류가 발생했다.
그래서 그 과정을 한 번 더 중첩해 발생하는 오류를 해결해줬다.

반복문이 너무 많이 사용돼서 코드가 비효율적이라는 생각이 들어 더 효율적인 방식을 고민해봤다.

2. 투포인터 : 훨씬 간단하다.
(다른 방향 진행 투포인터일 때, 정렬해주는 거 잊지 말기🤙🏻)
target index를 변수로 선언하고 left, right를 이용해 양쪽에서 접근한다.
left < right일 때만 반복문을 진행하는데
left와 right 합이 target보다 작으면 left++, target보다 크면 right--

합이 target과 같은 경우에는 left가 target index랑 같으면 left++, right가 target index랑 같으면 right--
➡️target index와 다른 두 index의 합으로 이루어져야 한다.

생각보다 시간 차이가 엄청 많이나네.. N 범위가 조금만 컸으면 오답 처리됐을 것 같다.
⭐⭐⭐배열에서 두 수의 합 = 투 포인터⭐⭐⭐

코드

sol 1) 빡구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N;
	int ans = 0;
	vector<int> v;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	for (int i = 0; i < v.size(); i++) {
		int target = v[i];
		for (int j = 0; j < v.size(); j++) {
			if (i == j)	continue;

			if (find(v.begin(), v.end(), target - v[j]) != v.end()) {
				int index = find(v.begin(), v.end(), target - v[j]) - v.begin();
				if (index != i && index != j) {
					ans++;
					break;
				}

				if (find(v.begin() + index + 1, v.end(), target - v[j]) != v.end()) {
					int index2 = find(v.begin() + index + 1, v.end(), target - v[j]) - v.begin();
					if (index2 != i && index2 != j) {
						ans++;
						break;
					}
				}

			}
		}
	}

	cout << ans;

	return 0;
}

sol 2) 투포인터

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[2001];

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

	int N;
	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + N);
	for (int i = 0; i < N; i++) {
		int target = arr[i];
		int left = 0, right = N - 1, sum;
		while (left < right) {
			sum = arr[left] + arr[right];
			if (target == sum) {
				if (left != i && right != i) {
					ans++;
					break;
				}
				else if (left == i)	left++;
				else if (right == i)	right--;
			}
			else if (sum > target)	right--;
			else left++;
		}
	}

	cout << ans;

	return 0;
}