백준 두 수의 합(3273) C++ 풀이

알고리즘 분류

정렬

두 포인터

문제 해결 아이디어

위 사진에서 알 수 있듯이 arr[L] + arr[R]를 더하여 숫자가 더 크면 작아져야 하므로 R를 왼쪽으로 이동시키고

더 작으면 커져야 하기 때문에 L을 오른쪽으로 이동시킨다. 또한 자기가 설정한 값이 같다면 L은 오른쪽, R은

왼쪽으로 시켜 다른 인덱스의 값이 설정한 값과 같은지 체크하면 된다.

 

코드

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

int n;
int arr[100000];
int target;
int result = 0;
int main()
{
	cin >> n;

	int left = 0, right = n - 1;

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

	cin >> target;

	sort(arr, arr + n);

	while (left < right)
	{
		if (arr[left] + arr[right] == target)
		{
			left++;
			right--;
			result++;
		}
		else if (arr[left] + arr[right] < target)
		{
			left++;
		}
		else if (arr[left] + arr[right] > target)
		{
			right--;
		}
	}

	cout << result;
}