💡 풀이
var pivotIndex = function (nums) {
let sum = 0;
for (let i = 0; i < nums.length; i++) sum += nums[i];
let leftSum = 0;
let rightSum = sum;
let pastPivot = 0;
for (let j = 0; j < nums.length; j++) {
let pivot = nums[j];
rightSum -= pivot;
leftSum += pastPivot;
if (leftSum === rightSum) return j;
pastPivot = pivot;
}
return -1;
};
let nums = [1, 7, 3, 6, 5, 6];
pivotIndex(nums);📝 정리
슬라이딩 윈도우 알고리즘(참고 링크)을 사용한 배열 문제다. 해당 알고리즘에 대해 매우 상세하게 정리된 링크이니 참고하도록 하자!
문제를 보면, pivot이 되는 index가 있고, 그 index를 기점으로 왼쪽에 있는 요소들의 합과 오른쪽에 있는 요소들의 합이 같아야 하는 pivot index를 찾아야 한다. (여기서 pivot index의 요소는 합계에 포함되지 않음)
이 때, O(N)의 시간 복잡도로 문제를 풀기 위해서는, Brute Force가 아닌 다른 방법을 사용해야 했는데(Brute Force는 O(N*N)의 시간복잡도를 가진다), 문제 해결 과정에서 Sliding Window 알고리즘을 참고하였다.
pivot index기준 왼쪽 요소들의 합계(=leftSum)는 pivot index의 요소를 포함하지 않아야 한다. 따라서 pastPivot이라는 이전의 pivot index를 기억하는 변수를 하나 만들어서,
leftSum += pastPivot 이라고 작성해준다.
오른쪽 요소들의 합계인 rightSum(=rightSum = sum)은
rightSum -= pivot 과 같이, 이전 pivot이 아닌 현재의 pivot을 계속 빼준다.
그러다 반복문 안에서 leftSum과 rightSum이 같아지는 지점이 올텐데, 그 때의 index가 바로 답이 된다.
만약 양쪽의 합계가 같아지는 순간이 없는 경우, 마지막에 -1을 return 해주면 된다.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/find-pivot-index/
