Find Pivot Index

• Reference
• Sliding Window 알고리즘을 익히기 좋은 문제다.
  • Sliding Window 알고리즘은 모든 수가 양수일 때 사용할 수 있는 알고리즘이다.

Algorithm

• 부르트 포스로 풀면 Pivot 이동 O(n) 연산과 해당 Pivot 시 발생하는 왼쪽, 오른쪽의 누적합 알고리즘이 합쳐진다면 O(n^2)이 예상된다.
• 하지만 Sliding Window 알고리즘을 적용하면, Pivot 이동 연산 O(n)과 오른쪽 합을 초기 총 합 O(n), 왼쪽 합을 초기 0으로 잡고, 오른쪽 합에 Pivot을 빼주는 연산, 왼쪽 합에 Pivot 값을 더해주는 연산을 O(1)을 수행하면 거즌 O(n)의 연산으로 마무리할 수 있다.
• 합이 Target 값을 갖는 SubArray를 찾는 문제로도 확장 가능하다.

Implementation

#include <iostream>
#include <vector>
#include <numeric>

int findPivotIdx(const std::vector<int> &v)
{
    int rightSum = std::accumulate(v.begin(), v.end(), 0);
    int leftSum = 0;
    int prevPivot = 0;

    for (int idx = 0; idx < v.size(); ++idx)
    {
        rightSum -= v[idx];
        leftSum += prevPivot;

        if (rightSum == leftSum)
            return idx;

        prevPivot = v[idx];
    }

    return -1;
}

int main()
{
    std::vector<int> v = {1, 8, 2, 9, 2, 3, 6};

    int pivotIdx = findPivotIdx(v);

    std::cout << "Pivot Index is : " << pivotIdx << std::endl;

    return 0;
}

Pivot Index is : 3