쿠키 구입

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> cookie) {
    int answer = 0;
    int acc = 0;
    int l, m, r;
    vector<int> sum;
    int size = cookie.size();
    int lSum, rSum;

    for (int i = 0; i < size; i++) {
        acc += cookie[i];
        sum.push_back(acc);
    }

    for (m = 0; m < size - 1; m++) {
        l = 0;
        r = size - 1;
        lSum = sum[m];
        rSum = sum[size - 1] - lSum;

        while (l < r && (lSum > answer || rSum > answer)) {
            if (lSum < rSum) {
                rSum -= cookie[r];
                r--;
            } else if (lSum > rSum) {
                lSum -= cookie[l];
                l++;
            } else {
                answer = answer < lSum ? lSum : answer;
                break;
            }
        }
    }

    return answer;
}

풀이

cookie 배열의 크기를 size에 저장
i를 0 ~ (size - 1)까지 1씩 증가시키는 반복문을 수행하여 0 ~ i번째 쿠키의 합을 구하여 sum 배열에 추가
m을 0 ~ (size - 2)까지 1씩 증가시키는 반복문을 수행하며 0 ~ m번째 쿠키의 합을 lSum, (m + 1) ~ (size - 1) 번째 쿠키의 합을 rSum에 저장.
(m + 1) ~ (size - 1) 번째 쿠키의 합은 0 ~ (size - 1) 번째 쿠키의 합에서 (0 ~ m) 번째 쿠키의 합을 빼주면 O(1)로 계산 가능
l을 0, r을 size - 1로 설정 후 l < r이며 (lSum > answer && rSum > answer)일 동안 반복문 수행
만약 lSum보다 rSum이 더 크면 rSum에 cookie[r]을 빼주고 r을 1 감소시킴
만약 rSum보다 lSum이 더 크면 lSum에 cookie[l]을 빼주고 l을 1 증가시킴
만약 lSum과 rSum이 같으면 answer와 lSum을 비교하여 최댓값을 answer에 저장 후 반복문 중단
이로써 좌우에서 줄여나가며 l ~ m번째 바구니의 과자 수와 (m + 1) ~ r번째 바구니의 과자 수를 맞춰나감

다른 방법

m을 0 ~ (size - 2)까지 1씩 증가시키는 반복문을 수행
lo, hi에 m을 저장
left에 m번째 바구니의 쿠키 개수 저장, right를 0으로 초기화
반복문을 수행하면서 left <= right일 경우 lo를 1 감소시키고 left에 lo번째 바구니의 쿠키 개수를 더함, left > right일 경우 hi를 1 증가시키고 right에 hi번째 바구니의 쿠키 개수를 더함
lo가 -1이 되거나 hi가 size가 될 경우 반복문 중단
left와 right가 같을 경우 answer과 left를 비교하여 최댓값을 answer에 저장

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49995