[BOJ] 1253번 좋다 (C++) [Do it!]

문제

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

풀이

투 포인터를 이용하여 풀이했다.
for문의 중첩으로 $O(N^2)$이 되는 상황을 $O(N)$으로 만든다.
(투 포인터 이전 정렬까지 포함되면 $O(NlogN)$)

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

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

	int N;
	cin >> N;
	vector<int> nums(N, 0);

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

	sort(nums.begin(), nums.end()); // 정렬

	int ans = 0;
	for (int check_idx = 0; check_idx < N; check_idx++) {
		long find = nums[check_idx];
		int left = 0;
		int right = N - 1;

		//투포인터 수행
		while (left < right) {
			if (nums[left] + nums[right] < find || left==check_idx) {
				left++;
			}
			else if (nums[left] + nums[right] > find || right==check_idx) {
				right--;
			}
			else {
				ans++;
				break;
			}
		}

	}

	cout << ans << "\n";
}