[LeetCode] - 724. Find Pivot Index

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Find Pivot Index" 문제입니다.

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

 

문제 : 

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.

---

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

 

Constraints :

• 1 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000

---

이 문제는 주어진 정수 배열 nums의 피벗 인덱스를 계산하고 찾아야 합니다. 피벗 인덱스는 인덱스의 왼쪽에 있는 모든 숫자의 합이 인덱스의 오른쪽에 있는 모든 숫자의 합과 같은 인덱스입니다.

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        
        int[] sumL = new int[n];
        int[] sumR = new int[n];

        sumL[0] = 0;
        for (int i = 1; i < n; i++) {
            sumL[i] = sumL[i-1] + nums[i-1];
        }

        sumR[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            sumR[i] = sumR[i + 1] + nums[i+1];
        }

        for (int i = 0; i < n; i++) {
            if (sumL[i] == sumR[i]) {
                return i;
            } 
        }
        
        return -1;
    }
}

 

제 코드는 정말 문제가 요구한 그대로를 직역한 코드라고 보시면 되겠습니다. 단계별로 설명을 드리자면 : 

1. 왼쪽 합 배열 (sumL) 계산 :
   • sumL의 첫 번째 요소를 0으로 초기화합니다. 이는 인덱스 0의 왼쪽에 요소가 없기 때문입니다.
   • 각 인덱스 i에 대해, sumL[i]는 sumL[i-1]에 nums[i-1]을 더한 값입니다. 이는 현재 인덱스의 왼쪽 합을 계산하는 과정입니다.
2. 오른쪽 합 배열 (sumR) 계산 :
   • sumR의 마지막 요소를 0으로 초기화합니다. 이는 마지막 인덱스의 오른쪽에 요소가 없기 때문입니다.
   • 각 인덱스 i에 대해, sumR[i]는 sumR[i+1]에 nums[i+1]을 더한 값입니다. 이는 현재 인덱스의 오른쪽 합을 계산하는 과정입니다.
3. 피벗 인덱스 찾기 :
   • sumL과 sumR 배열을 순회하며, 두 배열의 값이 같은 인덱스를 찾습니다.
   • 조건을 만족하는 인덱스를 찾으면 해당 인덱스를 반환합니다.
   • 조건을 만족하는 인덱스를 찾지 못하면 -1을 반환합니다.

이러면 굉장히 효율적이고 만족스러운 시간, 공간 복잡도가 나오는데요, 

• 시간 복잡도 : O(n)
  • sumL과 sumR 배열을 각각 계산하는 데 O(n) 시간이 걸립니다.
  • 이후, 피벗 인덱스를 찾기 위해 배열을 한 번 더 순회하므로 O(n) 시간이 추가됩니다.
  • 최종적으로, 전체 시간 복잡도는 O(n)입니다.

• 공간 복잡도 : O(n)
  • sumL과 sumR 두 개의 배열을 사용하므로, 추가적인 공간 복잡도는 O(n)입니다.
  • 여기서 n은 주어진 배열 nums의 길이입니다.

---

Runtime 결과