프로그래머스 Level 4 쿠키구입

쿠키구입 (프로그래머스 Level 4)

https://school.programmers.co.kr/learn/courses/30/lessons/49995

처음에는 완전탐색 방식으로 풀었으나,
시간초과 발생 후, 문제를 조금 더 분석해보았다

i~k 까지의 특정 부분의 합이
0부터 n번째 요소까지의 합인 sums에 집어넣은 후
sums[k] - sums[i] 를 통해 구할 수 있다는 점을 파악하고
원래 ‘부분합’에 관련된 문제인 것은 추측할 수 있었다

그렇기에
i~k , k + 1 ~ j 까지의 합을 추측하며
이를 이런식으로 풀어보았으나,

 totalSum = sums[j] - sums[i];
 for(int k = i; k < j;k++)
 {
	leftSum = sums[k] - sums[i];
	rightSum = totalSum - leftSum;

	if(leftSum == rightSum)
	{
		...
	}
 }

역시 비슷한 속도로 풀이가 되었다
‘공평’하게 둘로 나누어야 한다는 점에서
totalSum이 2 로 나뉘는지에 대한 여부도 생각을 해보았으나
여전히 O(n^3)을 벗어나지 못하였다

결국 검색을 해보니 ‘투 포인터’ 방식의 응용이 있어
그 부분을 보고서 이해할 수 있었다

부분합을 구한 후,
0~ cookie.size() 까지 (i) 각각에 대하여 투 포인터 방식으로 탐색하여
O(n^2) 복잡도를 가지도록 하는 법이다

1. left = i, right i + 1 에서 시작
   
2. 해당 인덱스에 따른 sums를 통해 왼쪽과 오른쪽의 부분합을 구한다
   
3. 두 합이 같은 경우 answer를 갱신해준다
   
4. 두 합 중 leftSum이 rightSum 이하면,
   left를 더 왼쪽에 배치함으로서, leftSum을 커지게 한다
   rightSum이 작은 경우는 right를 늘려 마찬가지로
   rightSum을 커지게 한다
   (점차 더 큰 answer가 있을 가능성을 탐색)
   

Code

#include <vector>
#include<math.h>

using namespace std;

int solution(vector<int> cookie) {
	const int cSize = cookie.size();
	int answer = 0;
	vector<int> sums(cSize + 1, 0);
	for (int i = 1; i <= cSize; i++)
	{
		sums[i] = sums[i - 1] + cookie[i - 1];
	}

	for (int i = 0; i < cSize; i++)
	{
		int left = i;
		int right = i + 1;
		while (left >= 0 && right < cSize)
		{
			int leftSum = sums[i + 1] - sums[left];
			int rightSum = sums[right + 1] - sums[i + 1];

			if (leftSum == rightSum)
			{
				answer = max(answer, leftSum);
			}

			if (leftSum <= rightSum)
			{
				left--;
			}
			else
			{
				right++;
			}
		}
	}

	return answer;
}