[LeetCode] 724. Find Pivot Index

문제

정수 배열 nums가 주어졌을 때, 이 배열의 pivot index를 구하세요.pivot index란, 해당 인덱스를 기준으로 왼쪽에 있는 모든 숫자의 합과 오른쪽에 있는 모든 숫자의 합이 '엄밀히' 같아지는 인덱스를 의미합니다.
만약 인덱스가 배열의 맨 왼쪽에 있다면, 왼쪽에는 어떤 원소도 없으므로 왼쪽 합은 0이 됩니다. 이것은 오른쪽 끝 인덱스에도 마찬가지로 적용되어, 오른쪽 합도 0이 됩니다.가장 왼쪽에 있는 pivot index를 반환하세요. 조건을 만족하는 인덱스가 없으면 -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

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

아이디어

public int pivotIndex(int[] nums) {
    for (int idx = 0; idx < nums.length; idx++) {
        int len = nums.length;
        int leftSum = 0;
        int rightSum = 0;

        if (idx != 0) {
            for (int left = 0; left < idx; left++) {
                leftSum += nums[left];
            }
        }

        if (idx != len -1) {
            for (int right = len - 1; right > idx; right--) {
                rightSum += nums[right];
            }
        }

        if (leftSum == rightSum) {
            return idx;
        }
    }
    return -1;
}

1차 결과

 

우선, 문제 이해가 어려웠다. pivot index 라는 개념에서 이해가 안됐다.

왼쪽과 오른쪽의 합을 더할 때, 피벗 인덱스를 포함하고 더해야 하는 줄 알고 작성했는데 피벗 인덱스를 제외하고 합을 비교해야 했다 ㅎ

일단 빠르게 1차로 풀고자 생각나는대로 작성해봤더니 성능 저 바다 저편이고 시간복잡도는 O(n 제곱) 수준이라 다른 방법 생각날듯말듯한데 2차로 풀 때도 답안보고 다시 풀어봐야 할 듯

1차는 매 인덱스마다 왼쪽과 오른쪽 합을 각각 for문으로 나눠서 계속 계산하기 때문에 개노답이지만 직독직해 수준으로 풀었다고 생각한다 ㅎ