Leetcode 704번 Find Pivot Index 해설

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

Find Pivot Index - LeetCode

724. Find Pivot Index

정수 배열이 주어지면 이 배열의 피벗 인덱스를 계산합니다.

피벗 인덱스는 인덱스 왼쪽에 있는 모든 숫자의 합이 인덱스 오른쪽에 있는 모든 숫자의 합과 같은 인덱스입니다.

인덱스가 배열의 왼쪽 가장자리에 있으면 왼쪽에 요소가 없기 때문에 왼쪽 합계는 0입니다. 이는 어레이의 오른쪽 가장자리에도 적용됩니다.

가장 왼쪽의 피벗 인덱스를 반환합니다. 그러한 인덱스가 없으면 -1을 반환합니다.

 

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

코드

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int left = 0;
        int total = 0;
        
        for(int i = 0; i < nums.size(); i++){
            total += nums[i];
        }
        
        for(int j = 0; j < nums.size(); j++){
            total -= nums[j];
            if(total == left){ // 오른쪽 값과 왼쪽의 값이 같은지 검사함
                return j;
            }
            left += nums[j];
        }
        
        return -1; //for문에서 찾지 못한경우 -1을 반환
    }
};

nums(배열)의 원소의 합을 구하여 total 에 넣은 상태에서

total에서 nums[0] 즉 nums의 첫번째 원소를 빼면 해당 원소 오른쪽의 원소의 값을 받아 올 수 있다

그 다음에  조건식에서 왼쪽과 오른쪽의 값이 같은지 검사한다 같다면 그 값이 pivot값(중심값)이 되는 것이다.

 

그 이후에 빼주었던 값을 left에 넣으면 왼쪽의 값이 된다.

이렇게 하지 않고 left를 total 뺌과 동시에 구하면 왼쪽의 원소가 하나더 늘어나는 샘이다.

 

위 처럼 하면 배열의 pivot을 o(n) 의 timecomplexity로 찾을 수 있는 방안이다.

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문