[0x14] 투 포인터

배열에서 원래 이중 반복문으로 O(N²)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 많다. 반대로 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우도 많다.

 

구현할 때 가장 많이 실수하는게 인덱스 하나 차이로 어긋나는 것들이다.

 

 

연습 문제

 

2230: 수 고르기

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[100001];
int st, en;
int answer = 1<<30;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

	sort(arr, arr + n);

	while (en < n)
	{
		if (arr[en] - arr[st] >= m)
		{
			answer = min(answer, arr[en] - arr[st]);
			st++;
		}
		else
			en++;
	}

	cout << answer;

	return 0;
}

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[100001];
int answer = 1<<30;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

	sort(arr, arr + n);

	int en = 0;
	for (int st = 0; st < n; ++st)
	{
		while (en < n && arr[en] - arr[st] < m) en++;
		if (en == n) break;
		answer = min(answer, arr[en] - arr[st]);
	}

	cout << answer;

	return 0;
}

 

바킹독님의 풀이

 

1806: 부분합

#include <iostream>

using namespace std;

int n, s, tot;
int arr[100001];
int answer = 100001;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

	tot = arr[0];
	int en = 0;
	for (int st = 0; st < n; ++st)
	{
		while (en < n && tot < s)
		{
			en++;
			if (en != n) tot += arr[en];
		}
		if (en == n) break;
		answer = min(answer, en - st + 1);
		tot -= arr[st];
	}

	// 아무것도 찾지 못해 답이 0인 경우가 있음
	if (answer == 100001) answer = 0;

	cout << answer;

	return 0;
}

 

위의 문제와 다르게 해가 없을수도 있어서 예외처리가 마지막에 필요하다.

 

기본 문제

 

1644: 소수의 연속합

#include <iostream>
#include <vector>

using namespace std;

int n, tot, answer;
vector<int> prime;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	if (n == 1)
	{
		cout << 0;
		return 0;
	}

	vector<bool> b(n + 1, true);
	for (int i = 2; i * i <= n; ++i)
	{
		if (!b[i]) continue;
		for (int j = i * i; j <= n; j += i)
			b[j] = false;
	}

	for (int i = 2; i <= n; ++i)
		if (b[i]) prime.push_back(i);

	auto si = prime.begin();
	auto ei = prime.begin();
	tot = prime.front();

	while (ei != prime.end())
	{
		if (*si == n && *ei == n)
		{
			answer++;
			break;
		}
		if (tot == n)
		{
			answer++;
			tot -= *si;
			si++;
		}
		else if (tot < n)
		{
			ei++;
			if (ei != prime.end())
				tot += *ei;
		}
		else
		{
			tot -= *si;
			si++;
		}
	}

	cout << answer;

	return 0;
}

 

2003: 수들의 합 2

#include <iostream>

using namespace std;

int n, m, tot, answer;
int arr[10001];
int st, en;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;

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

	tot = arr[0];

	while (en < n)
	{
		if (tot == m)
		{
			answer++;
			tot -= arr[st];
			st++;
		}
		else if (tot > m)
		{
			tot -= arr[st];
			st++;
		}
		else
		{
			en++;
			if (en < n) tot += arr[en];
		}
	}

	cout << answer;

	return 0;
}

 

tot으로 매번 합해서 값을 가지고 있어도 되고 prefix sum을 이용해도 된다.