프로그래머스 문제 - 쿠키 구입

프로그래머스 쿠키 구입 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

1번부터 N번까지 차례로 번호가 붙은 바구니가 나열되어 있으며 그 안에는 과자들이 들어 있습니다.
첫째는 l번째부터 m번째까지, 둘째는 m+1번째부터 r번째까지 바구니를 주게 됩니다. (1 <= l <= m, m+1 <= r <= N)
바구니를 받은 두 아들의 과자 수는 같아야 합니다.
두 아들이 받을 수 있는 과자 수의 최대값을 구해야합니다.

문제 풀이

첫 번째 아들한테 바구니를 주고 두 번째 아들한테 바구니를 주며 하나씩 확인해봐도 답이 나오지만, 바구니가 최대 2000개를 가지기에 시간초과가 나옵니다.
문제를 해결하는 여러 방법 중 한 인덱스를 기준으로 왼쪽 오른쪽을 검사하며 과자의 수를 비교하는 방법을 사용하였습니다.

기준점의 인덱스에 있는 바구니를 첫 번째 아들에게 주고 다음 바구니를 두 번째 아들에게 준 후 과자의 수를 비교합니다.
만약 첫 번째 아들이 두 번째 아들보다 과자가 적다면 마지막으로 받은 바구니의 위치의 앞에 바구니를 추가로 준 후 비교합니다.
만약 두 번째 아들이 첫 번째 아들보다 과자가 적다면 마지막으로 받은 바구니의 위치의 뒤에 바구니를 추가로 준 후 비교합니다.
만약 두 아들의 과자가 같다면 전에 찾았던 최대값과 비교하여 큰 값을 저장해줍니다. 이후에 바구니를 더 주며 최대값이 존재하는지 확인합니다.

만약 1, 1, 2, 3의 배열을 주고 기준점이 1이라면
1번째 바구니를 첫번째 아들한테 주고 그 다음 바구니를 두 번째 아들에게 전해준 후 과자의 수를 비교합니다.
1, 2이기 때문에 첫 번째 아들의 과자 수가 적기 때문에 1번째의 앞 바구니인 0번째 바구니의 과자를 준 후 비교합니다.
2, 2이기 때문에 최대값을 비교 후 큰 값을 저장해줍니다. 양쪽으로 바구니가 더 있다면 추가로 바구니를 더해줍니다.
없으므로 다음 기준점으로 옮긴 후 계산해줍니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int maxSum = 0;
    
    for(int i = 0; i < cookie.size()-1; i++)
    {
        //한 인덱스를 기준으로 두 아들한테 바구니의 과자만큼 더해줌
        int leftIndex = i;
        int rightIndex = i+1;
        int leftSum = cookie[leftIndex];;
        int rightSum = cookie[rightIndex];
        while(true)
        {
            if(leftSum > rightSum)  //첫 번째 아들이 더 작을 경우
            {
                rightIndex++;
                if(rightIndex >= cookie.size())
                {
                    break;
                }
                rightSum += cookie[rightIndex];
            }
            else if(leftSum < rightSum)  //두 번째 아들이 더 작을 경우
            {
                leftIndex--;
                if(leftIndex < 0)
                {
                    break;
                }
                leftSum += cookie[leftIndex];
            }
            else    //과자의 수가 같을 경우
            {
                maxSum = max(maxSum, leftSum);
                leftIndex--;
                if(leftIndex < 0)
                {
                    break;
                }
                leftSum += cookie[leftIndex];
            }
        }
        answer = max(answer, maxSum);
    }
    
    return answer;
}

출처

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