[PrefixSum][Easy] 724. Find Pivot Index

https://leetcode.com/problems/find-pivot-index/description

Find Pivot Index - LeetCode

 

Q. 특정 index를 기준으로, 우측과 좌측의 합이 같다면, 이 index를 피봇 index라 한다. 이 피봇 index를 찾아라.

 

Solution. 

 보통 알고리즘 문제 풀이는 TC를 O(N)가 되도록 풀면, 대체로 옳은 답인 경우가 많다. 여기세 in-place로 풀라고 한다거나 그런 식이다. 

 이 문제도 추가 버퍼를 사용하여 미리 합을 저장해 놓으면 이를 이용해서 쉽게 해결이 가능하다. 

 

int pivotIndex(vector<int>& nums)
{
    vector<int> leftSum, rightSum;
    for (int k = 0; k < nums.size(); ++k)
    {
        if (leftSum.size() == 0)	leftSum.push_back(0);
        else leftSum.push_back(leftSum[leftSum.size() - 1] + nums[k - 1]);

        int r = nums.size() - 1 - k;
        if (rightSum.size() == 0)	rightSum.push_back(0);
        else rightSum.push_back(rightSum[rightSum.size() - 1] + nums[r + 1]);
    }

    for (int k = 0; k < nums.size(); ++k)
    {
        if (leftSum[k] == rightSum[nums.size()-1-k])
            return k;
    }
    return -1;
}