LeetCode / Prefix Sum / 724번 / Find Pivot Index / JS

< 문제 바로가기 >

Find Pivot Index - LeetCode

 

< 문제 간단설명 >

nums 배열에서 한 index를 pivot으로 삼았을 때, 그 pivot의 왼쪽에 있는 값들을 다 더한 값과 오른쪽에 있는 값들을 다 더한 값을 비교해서 같다면 그 pivot의 index를 return 하면 되는 문제이다.

 

[1,7,3,6,5,6]

예를들어 위와 같은 배열이 있다고하면, index 3인 6을 기준으로 왼쪽에 있는 모든 값인 1, 7, 3을 다 더하면 11이다.

마찬가지로 오른쪽에 있는 모든 값인 5, 6을 더하면 11이다.

이렇게 양쪽의 합이 같다면 6이 위치인 3을 return 해준다.

 

/**
 * @param {number[]} nums
 * @return {number}
 */
 var pivotIndex = function(nums) {
  let leftSum = 0;
  let rightSum = nums.reduce((acc, cur) => acc + cur);

  let result = -1;
  
  for(let i=0; i<nums.length; i+=1) {
      let cur = nums[i];
      
      rightSum -= cur;

      if(leftSum === rightSum) {
          result = i;
          break;
      }

      leftSum += cur;
  }

  return result;
};

---

pivot이 될 index는 반복문을 이용해서 계속 위치를 바꿔주면 된다.

하지만 여기서 핵심은 pivot이 바뀔 때 마다 왼쪽과 오른쪽의 합을 새로 계속 구해주는 것이 아니다.

 

처음에 pivot이 -1이라고 하면 오른쪽의 합은 배열의 모든 값을 더한 합일 것이다.

왼쪽의 합은 0일것이다.

 

그 다음으로 pivot이 배열의 0번째 인덱스라면 오른쪽의 합은 0번째 값을 뺀 합일 것이다.

왼쪽의 합은 여전히 0일것이다.

 

그 다음으로 pivot이 배열의 1번째 인덱스라면 이전의 오른쪽의 합에서 1번째 값을 뺀 합일 것이다.

왼쪽의 합은 0번째 값을 더해준 값일 것이다.

 

따라서 위와 같은 규칙을 적용해보면 pivot 오른쪽의 합은 전체의 합에서 현재 pivot의 값을 계속해서 빼주면 된다.

pivot 왼쪽의 합은 현재 pivot 이전의 값을 계속해서 더해주면 된다. (pivot은 합에 미포함이기 때문)