투 포인터 개념을 이용한 문제풀이 - 연속된 자연수의 합 구하기

* Do it 코딩테스트 책을 참고하였습니다.

 

투 포인터라는 개념을 이용하면 시간 복잡도를 줄일 수 있습니다. 투 포인터란  연속된 숫자의 양 끝점의 인덱스를 변수로 가지고, 두 점을 이용하여 배열을 이동해나가며 두 인덱스 사이의 값이 원하는 값이 되는지를 확인하며 탐색하는 방법이다.

 

두 끝점(i,j)가 있고, i <= j인 경우 i가 한 칸 움직이는 것은 arr[i]의 값을 빼준다는 의미가 되고,  j가 한 칸 움직이는 것은 arr[j+1]의 값을 더해준다는 것이다.더해나가며 i와 j사이의 숫자의 합이 원하는 값과 일치하면 j의 값을 한칸 움직여 그 다음 경우의 수를 탐색해나가는 것이 이 함수의 구조이다.

void solution_006()
{
	int start_index = 1;
	int end_index = 1;

	int sum = 1;
	int N = 15;

	int count = 1;
	while (N != end_index)
	{
		if (sum > N)
		{
			sum -= start_index;
			start_index++;
		}
		else if (sum < N)
		{
			end_index++;
			sum += end_index;
		}
		else
		{
			count++;
			end_index++;
			sum += end_index;
		}
	}

	cout << count;
}