[LeetCode] 724번: Find Pivot Index - Java

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

Find Pivot Index - LeetCode

문제 설명

피봇 인덱스는 해당 인덱스를 기준으로 배열의 좌측의 합과 우측의 합이 같은 인덱스를 뜻한다. 이 피봇 인덱스를 구하면 된다.

풀이 방법 1: 이중 반복문 - O(n^2)

단순히 이중 반복문을 순회하면서 왼쪽의 합과 오른쪽 합을 전부 구해서 해결할 수 있다.

public int pivotIndex(int[] nums) {

    int answer = -1;

    for (int pivotIdx = 0; pivotIdx < nums.length; pivotIdx++) {
        int leftSum = 0;
        int rightSum = 0;

        for(int left = pivotIdx; left < pivotIdx; left++)
            leftSum += nums[left];
        
        for (int right = nums.length - pivotIdx; right < nums.length; right++)
            rightSum += nums[right];

        if (leftSum == rightSum) answer = i;
    }

    return answer;
}

풀이 방법 2: 슬라이딩 윈도우 - O(n)

위 방법 대신 슬라이딩 윈도우 기법을 사용하면 효율적인 코드를 작성할 수 있다.

먼저 배열의 합계를 모두 구해 놓는다. 여기서 요소 개수만큼 반복하므로 O(n)이 소요된다.

그리고 반복문을 돌면서 총합에서 좌측의 요소들을 빼나간다. 그러다 좌측의 합과 우측의 합이 같아지면 반복을 종료하고 정답을 반환한다. 여기서 O(n)이 소요된다. 따라서 O(n) + O(n)이 되므로 최종 시간복잡도는 O(n)이 된다. 그림으로 표현하면 다음과 같다. 아래처럼 일정한 크기로 이동하는 방식을 슬라이딩 윈도우라고 한다. 창문을 미는 것처럼 창문 크기는 그대로지만 위치가 변하는 것이다.

코드는 다음과 같다.

public int pivotIndex(int[] nums) {
    int leftSum = 0;
    int rightSum = Arrays.stream(nums).sum();

    int answer = -1;
    int tmp = 0;

    for (int pivotIdx = 0; pivotIdx < nums.length; pivotIdx++) {
        leftSum += tmp;
        rightSum -= nums[pivotIdx];

        if (leftSum == rightSum) {
            answer = pivotIdx;
            break;
        }

        tmp = nums[pivotIdx];
    }

    return answer;
}