[LeetCode] 724 Find Pivot Index JavaScript

문제 링크

Find Pivot Index - LeetCode

 

문제 유형

배열 (Array)

 

문제 풀이

처음에는 브루트 포스로 현재 피봇의 양옆의 값들의 합을 비교하는 방법이 떠올랐다. 그러나 이렇게 되면 양옆의 값을 더할 때 O(n)의 시간복잡도를 갖게 되고, 이것이 n개 만큼 반복되어 결국 O(n^2)의 시간복잡도를 갖게 되므로 다른 방법으로 접근해야 한다.

이 문제는 배열 접근 방법 중 하나인 sliding 기법을 사용하면 된다.

먼저, 배열 요소들의 전체 합을 구한다. 그리고 배열을 순회하면서 피봇 왼쪽의 합을 저장하는 변수에는 이전 pivot 값을 더하고, 피봇 오른쪽의 합을 저장하는 변수에는 현재 pivot 값을 뺀다. 그리고 현재 pivot의 왼쪽 합과 오른쪽 합을 비교하여 합이 같으면 해당 pivot의 인덱스를 출력하면 된다. 따라서, 전체합을 구하는데 O(n)의 시간복잡도를 갖고, 배열을 순회하며 왼쪽의 합, 오른쪽의 합을 구할때 O(n)의 시간복잡도를 가지므로 총 O(n)의 시간복잡도를 갖게 된다.

 

코드

var pivotIndex = function(nums) {
    // 배열 요소의 전체 합을 구한다.
    let rightSum = nums.reduce((acc, cur) => acc + cur, 0);
    
    let leftSum = 0;
    for (let i = 0; i < nums.length; i++) {
        leftSum += i == 0 ? 0 : nums[i - 1]; // left sum에 이전 pivot 값을 더한다.
        rightSum -= nums[i]; // 전체 sum에 pivot 값을 뺀다.
        if (leftSum === rightSum) { // 값 비교
            return i;
        }
    }
    return -1;
};

 

참고

https://www.youtube.com/watch?v=6gQm5De94aU&list=PLDV-cCQnUlIYFOXYzqLoXnEye4WxDa_30&index=5