투 포인터 개념을 이용한 문제 풀이 - '좋은 수' 구하기

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

 

해당 문제는 백준 온라인 저지 1253번 입니다. (문제에 대한 설명은 생략하도록 하겠습니다.)

 

해당 문제도 투 포인터 개념을 이용한 문제입니다. 모든 수에 대해서 검사를 해야하므로 N만큼의 계산이 들어가고 N개의 숫자에 대해서 투 포인터 개념을 이용하여 두 수의 합의 조합을 찾아야 하므로  O(nLogN)의 시간 복잡도를 지니게 됩니다.

 

정리하면, 

1. 모든 수에 대해 검사한다.

2. N을 만들 수 있는 두 수의 조합이 존재하는지 검사한다.

라고 할 수 있을 것 같습니다.

 

어렵지 않은 개념이므로 추가 설명없이 코드 올리도록 하겠습니다.

void solution_008()
{
	vector<int> list = { 1,2,3,4,5,6,7,8,9,10 };
	sort(list.begin(), list.end());

	int count = 0;
	for (int i = 0; i < list.size(); i++)
	{
		int start = 0;
		int end = i;

		int n = list[i];

		while (start < end)
		{
			int sum = list[start] + list[end];
			if (sum == n)
			{
				count++;
				break;
			}
			else if (sum > n)
			{
				end--;
			}
			else
			{
				start++;
			}
		}
	}
	cout << count;
}

생각해보니 코드에 대한 설명이 없어서 이해가 안 되시는 부분은 댓글로 알려주세요! 

이렇게 문제를 마무리하겠습니다. 포바~!