투 포인터를 이용한 문제 풀이 - 주몽의 망령

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

 

해당 문제는 백준 온라인 저지 1940번 문제입니다.

 

간단하게 설명하자면, 배열로 주어지는 자연수 값 ( 1<= N <= 15000) 중, 2개를 선택하여 더한 값이 M이 되는 값이 몇 쌍이 존재하는 지를 구하는 문제입니다.

 

우선적으로, 해당 문제를 손쉽게 풀기 위해서 오름차순으로 배열을 정리할 필요가 있습니다.

 

C++의 <algorithm> 헤더파일을 추가하면, 아래 코드에서 사용한 vector 컨테이너에 대해서 손쉽게 정렬할 수 있습니다.

 

vector<int> arr {2,5,3,1};
sort(arr.begin(),arr.end());

 

-> arr이라는 vector컨테이너의 begin (시작부분을 나타내는 iterator) 에서 end (끝 부분을 나타내는 iterator)의 값을 넣어주면 arr에 존재하는 모든 원소에 대해서 기본값으로 오름차순으로 정렬해주게 됩니다. 만약 배열의 원소의 타입이 사용자 정의 타입이라거나, 원하는 다른 정렬 방법이 있다면 정렬을 해줄 수 있는 bool 타입 함수를 작성하여 3번째 매개변수로 넣어주면 됩니다.

 

ex.

bool cmp(int Left , int Right)
{
	return Left < Right;
}

sort(arr.begin(), arr.end(), cmp);

 다시 문제로 돌아와서, 오름차순으로 정렬된 배열의 양 끝점 , 즉 n개의 원소중 0번 인덱스와 n-1번 인덱스를 잡고, 해당 인덱스의 원소값들의 합을 M과 비교하며 더하고 빼주며 검색을 이어갑니다.

 

M값보다 합이 작다면, start부분의 인덱스를 1만큼 올려주면 오름차순으로 정렬된 배열이므로 두 인덱스의 원소합이 자연스럽게 더 커지게 됩니다. 반대의 경우에는 end부분의 인덱스를 1만큼 내려서 합의 크기를 줄일 수 있습니다. 만약, 합의 크기가 M과 동일하다면 조건을 만족하는 쌍 1개를 찾은 것을 의미하므로, count의 개수를 1만큼 증가시키고 그 다음 경우를 따지기 위해 start와 end의 인덱스를 각각 1만큼씩 이동방향으로 증감시켜줍니다. 이렇게 start < end를 만족하는 모든 인덱스에 대해 탐색이 끝나면 찾을 수 있는 모든 경우의 수를 찾은 것이 되므로, 함수를 종료하고 결과값을 반환/출력하면 답이 나오게 되는 방식입니다.

 

아래는 위의 설명을 토대로 작성한 코드입니다. (헤더파일은 생략하였으므로 필요한 것들을 꼭 추가하여야 합니다.)

void solution_007()
{
	vector<int> list = { 2,7,4,1,5,3 };
	int M = 9;

	int start = 0;
	int end = list.size()-1;

	sort(list.begin(), list.end());

	int count = 0;

	while (start < end)
	{
		if (list[start] + list[end] > M)
		{
			end--;
		}
		else if (list[start] + list[end] < M)
		{
			start++;
		}
		else
		{
			count++;
			start++;
			end--;
		}
	}	

	cout << count;
}

 

이상으로 문제에 대한 설명을 마치도록 하겠습니다. 포바~!