Find Pivot Index

주어진 배열에서 Pivot Index를 찾아라.
Pivot이란 배열 상에 있는 값들 중, 임의의 인덱스를 중심으로 왼쪽과 오른쪽의 합이 같은 지점의 인덱스이다.

예 : [ 1, 8 , 2, 9, 2, 3, 6 ]  --> Pivot : 9

개념

• 배열을 순회하는 인덱스를 중심으로  좌, 우의 값들의 합을 계산한다. ( LeftSum, RightSum )
• LeftSum과 RightSum이 동일하면 해당 인덱스가 Pivot 이다. (종료)
• LeftSum과 RightSum 이 다르면 순회를 계속 진행하되 이전 인덱스의 값을 저장한다. (PastPivotNum)

 

#include <iostream>

int accumulation(int* nums, int numSize)
{
    int resultSum = 0;
    for (int i = 0; i < numSize; i++)
    {
        resultSum += nums[i];
    }

    return resultSum;
}

int pivotIndex(int* nums, int numSize)
{
    // 입력 값의 전체 합
    int sum = accumulation(nums, numSize);

    // 피봇 왼쪽의 합
    int leftSum = 0;  
    // 피봇 오른쪽의 합
    int rightSum = sum;

    int pastPivotNum = 0;
    for (int i = 0; i < numSize; i++)
    {
        int num = nums[i];  // 현재 인덱스의 값
        rightSum = rightSum - num; // 오른쪽의 합은 이전 오른쪽의 합에서 현재 인덱스의 값을 뺀 것이다.
        leftSum = leftSum + pastPivotNum;   //왼쪽의 합은 이전 현재 값에서 피봇의 값을 더한 것.

        // 피봇을 찾은 결과
        if (leftSum == rightSum)
        {
            return i;
        }
        // 이전 피봇 값 저장.
        pastPivotNum = num;
    }

    // 피봇을 찾지 못한 경우
    return -1;
}

int main()
{
    int InputValus[7] = { 1, 8 , 2, 9, 2, 3, 6 };
    int result = pivotIndex(InputValus, 7);

    std::cout << "result : " << result << std::endl;
}