[LeetCode] 724. Find Pivot Index(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

Find Pivot Index - LeetCode

[문제 설명]

Given an array of integers nums, calculate the pivot index of this array.
The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.
If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.
Return the leftmost pivot index. If no such index exists, return -1.

[제한 사항]

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

[입출력 예]

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

[문제 풀이]

✅ 노트에 입출력 예를 써가며 로직을 구상했다.

피벗 인덱스의 왼쪽 인덱스의 숫자들의 합과 피벗 인덱스의 오른쪽 인덱스의 숫자들의 합이 같을 때
➜ 해당하는 피벗 인덱스를 리턴하면된다.

고려할 부분 :
만약 피벗 인덱스가 가장 왼쪽에 있다면 왼쪽에는 이전 숫자들이 없기 때문에 이전 숫자들의 합은 0이다.
만약 피벗 인덱스가 가장 오른쪽에 있다면 오른쪽에는 이후 숫자들이 없기 때문에 이후 숫자들의 합은 0이다.

입출력 예1 [1, 7, 3, 6, 5, 6] 으로 코드를 설명해보자면

먼저 초기 왼쪽 인덱스의 숫자들의 합을 0(left 변수)
오른쪽 인덱스의 숫자들의 합을 배열의 모든 원소를 더한 값인 28(right 변수)
피벗 인덱스 위치 이전의 값을 저장할 변수를 0(beforeNum 변수)으로 초기화한다.

현재 피벗 인덱스 위치가 0이면
left 변수에 피벗 인덱스 위치 이전의 값(0)을 더해준다.
right 변수에는 피벗 인덱스 위치 0의 값(1)을 빼준다.
피벗 인덱스를 기준으로 왼쪽 인덱스 합(0)과 오른쪽 인덱스 합(27)이 다르기 때문에 피벗 인덱스 위치를 이동한다.
그리고 beforeNum변수를 현재 피벗 인덱스 위치의 값(1)으로 변경해준다.

피벗 인덱스 위치가 1이면
left 변수에 피벗 인덱스 위치 이전의 값(1)을 더해준다.
right 변수에는 피벗 인덱스 위치 1의 값(7)을 빼준다.
피벗 인덱스를 기준으로 왼쪽 인덱스의 합(1)과 오른쪽 인덱스의 합(20)이 다르기 때문에 피벗 인덱스 위치를 이동한다.
그리고 beforeNum변수를 현재 피벗 인덱스 위치의 값(7)으로 변경해준다.

피벗 인덱스 위치가 2이면
left 변수에 피벗 인덱스 위치 이전의 값(7)을 더해준다.
right 변수에는 피벗 인덱스 위치 2의 값(3)을 빼준다.
피벗 인덱스를 기준으로 왼쪽 인덱스의 합(8)과 오른쪽 인덱스의 합(17)이 다르기 때문에 피벗 인덱스 위치를 이동한다.
그리고 beforeNum변수를 현재 피벗 인덱스 위치의 값(3)으로 변경해준다.

피벗 인덱스 위치가 3이면
left 변수에 피벗 인덱스 위치 이전의 값(3)을 더해준다.
right 변수에는 피벗 인덱스 위치 3의 값(6)을 빼준다.
피벗 인덱스를 기준으로 왼쪽 인덱스의 합(11)과 오른쪽 인덱스의 합(11)이 같기 때문에 현재 피벗 인덱스 위치를 리턴하면 된다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/LeetCode: LeetCode for Coding Test

class Solution {
public:
    vector<int> result;
    int pivotIndex(vector<int>& nums) {
        int total_sum = 0;
        for(int element : nums) {
            total_sum += element;
            result.emplace_back(total_sum);
        }

        int len = result.size();
        int right = result[len - 1];
        int left = 0;
        int beforeNum = 0;
        int pivotidx = -1;
        for(int i = 0; i < len; ++i) {
            left += beforeNum;
            right -= nums[i];
            if(left == right) {
                pivotidx = i;
                break;
            }  
            beforeNum = nums[i];
        }
        return pivotidx;
    }
};