[LeetCode 코테 풀기] 724. Find Pivot Index

사용 언어 : JavaScript

문제 : 

https://leetcode.com/problems/find-pivot-index/

Find Pivot Index - LeetCode

 

내 풀이 :

왼쪽의 요소에 하나씩 접근하면서 합계를 구하고, 오른쪽의 합과 동일한지 확인하면 될 것 같긴한데..

const pivotIndex = function(nums) {
    let pivot = 0;
    while (pivot < nums.length) {
        let leftSum = 0;
        let rightSum = 0;
        for (let i = 0; i < pivot; i++)
            leftSum += nums[i];
        for (let i = (nums.length - 1); i > pivot; i--)
            rightSum += nums[i];
        if (leftSum === rightSum)
            return pivot;
        else
            pivot++;
    }
    return -1;
};

for문을 너무 많이 사용해버렸다.

더구나 반복문을 중첩하기까지..

 

 

가장 많은 투표를 받은 풀이 :

 

첫번째 풀이.

https://leetcode.com/problems/find-pivot-index/discuss/311803/JavaScript-Easy-to-understand-solution

[JavaScript] Easy to understand solution - LeetCode Discuss

 

풀이를 해석해보면 다음과 같다.

1. reduce 메서드를 이용해서 전체 총합을 구한다.

2. 전체 총합에서 왼쪽의 요소(0, 1, 2, ...)를 하나씩 뺀다. 그 값은 right 변수에 저장한다.

3. 2에서 뺐던 왼쪽의 요소들은 left 변수에 누적해서 저장한다.

4. 둘을 비교해서 일치하면 현재의 인덱스를 반환한다.

    -> 일치하지 않으면 반복문은 계속 돈다.

 

이 방법을 이용하면 시간 복잡도가 O(n)이 된다.

공간 복잡도는 O(1)이 된다. (문제에서 제시된 nums 제외)