투포인터(two pointer)

가가오 문제 중 투포인터가 나왔다 필자는 투포인터라는 존재를 모른채 이진 탐색 문제인줄 알고 오지게 삽질하다가 못풀었다. 그래서 그 분노로 투포인터에 대해 공부하고 백준 문제 4문제 정도를 풀었다. 

 

투 포인터는 이름 그대로 두개의 점을 사용하여 연속된 수의 집합의 합 및 개수들을 구할 수 있게 해준다. 여기서 주의 할 점은 연속된 집합이다. 

 

시작은 start, end 둘다 첫 요소를 가리키며 시작한다. 목표하는 숫자에 비해 작으면 end를 계속 늘려가주며 더해준다. 그러다 목표하는 숫자에 비해 커지거나 같아지면 start요소의 값을 빼주고 start를 늘린다. 사실 글만 보면 어떤 느낌인지 느낌이 안올 것이다. 그래서 그림을 준비했다. 

 

 

위 그림을 통해서도 알 수 있지만 크게 생각할 점은 두가지다. 

 

집합의 핪 값이 작다면 end를 늘려가며 계속 더 해주고 

여기서 더한 값이 찾을 숫자보다 같거나 커지면 start에 해당하는 숫자의 값을 빼주고 start를 1늘려주면 된다. 

 

그리고 반복문의 조건문은 end가 끝에 도달하면 끝나게 된다. start가 덜 돌았는데 끝나면 안되는거 아닌가라고 생각할 수 있지만 잘 생각해보면 end가 마지막에 도달한 후 이제 sum은 더 이상 커질 수 없다. 그래서 sum이 찾는 값보다 한번이라도 작아지면 더 이상 start를 사용할 수 없다 왜냐 start로 계속 빼봤자 sum은 계속 작아질 거기 때문에 그리고 뒤에 더 이상 숫자도 없어서 값이 더 커질 수도 없다. 따라서 연산할 필요가 없다.

 

가장 기본적인 문제이다. 

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

2003번: 수들의 합 2

이 문제에서 좌표를 추가하는 코드를 작성했다.

#include <cstdio>
#include <vector>

using namespace std;

long long N, M;
long long mArray[10003];
vector<pair<int, int> > position;
long long getSum();

int main(){
	scanf("%lld %lld", &N, &M);
	for(int i = 0; i < N; i++)
		scanf("%lld", &mArray[i]);
	printf("%lld\n", getSum());
	for (auto p : position)
		printf("%d %d\n", p.first, p.second);
}

long long getSum(){
	int start = 0, end = 0;
	long long sum = 0, result = 0;
	while(end <= N ){ //end가 끝에 도달 한 후 start를 빼봤자 소용없을 때 종료
		if(sum < M){ // end 더함
			sum += mArray[end];
			end++;
		}else if(sum >= M){ // 크거나 같아지면 start 부분 제거
			sum-=mArray[start];
			start++;
		}
		if(sum == M){ //값을 찾음
			position.push_back(make_pair(start, end-1));
			result++;
		}
	}
	return result;
}