Prefix sum

문제링크: https://leetcode.com/problems/running-sum-of-1d-array/description/

 

주어진 정수 배열 nums에 대해,
각 인덱스 i에서의 누적합(running sum)을 계산하라.

즉, runningSum[i] = nums[0] + nums[1] + ... + nums[i]

→ 이를 모든 인덱스에 대해 구한 배열을 반환하는 문제.

 

제약사항

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

누적합의 범위: -10^9 ~ 10^9 => int로 커버 가능

class Solution {
    public int[] runningSum(int[] nums) {
        int[] answer = new int[nums.length];
        answer[0] = nums[0];
        for(int i = 1; i < answer.length; i++){
            answer[i] = answer[i - 1] + nums[i];
        }

        return answer;
    }
}

 

 

문제링크: https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/description/

 

정수 배열 nums가 주어지고, 양의 정수 startValue부터 시작하여 왼쪽에서 오른쪽으로 누적합(step-by-step sum)을 계산한다.

이 누적합이 항상 1 이상이 되도록 하는 최소의 startValue를 구하는 문제.

 

제약사항:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

아이디어: 앞으로의 변화량(누적합)의 최솟값을 구한다. 그 값이 음수면 양수화 + 1, 아니면 1

class Solution {
    public int minStartValue(int[] nums) {
        int min = nums[0];
        int curr = nums[0];
        for(int i = 1; i < nums.length; i++){
            curr += nums[i];
            min = Math.min(min, curr);
        }

        if (min < 0) return Math.abs(min) + 1;
        return 1;
    }
}

 

 

 

문제링크: https://leetcode.com/problems/k-radius-subarray-averages/description/

 

정수 배열 nums와 정수 k가 주어진다.

각 인덱스 i에 대해, i를 중심으로 반경 k까지 양쪽으로 총 2k + 1개의 요소가 존재하면

해당 구간의 평균을 정수 나눗셈으로 계산해 저장한다.

그렇지 못하면 -1을 저장한다.

 

nums.length가 최대 100,000이므로 O(n^2) 미만으로 풀어야 합니다.

nums의 원소와 k의 범위는 0 ~ 100,000입니다.

그래서 nums의 원소를 최대 2k+1번 더하기 때문에 sum의 최댓값이 10^5 * (2*10^5 + 1) = 2*10^10 + 10^5 이기 때문에 int로는 담을 수 없습니다. long으로 담아야합니다.

 

아이디어: 누적합으로 푼다면 answer[i] = (psum[i+k] - psum[i-k] + nums[i-k]) / (2*k+1)

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int[] answer = new int[nums.length];
        long[] psum = new long[nums.length];
        psum[0] = nums[0];

        for(int i = 1; i < psum.length; i++){
            psum[i] = psum[i-1] + nums[i];
        }

        int range = 2 * k + 1;
        for(int i = 0; i < answer.length; i++){
            if (i-k < 0 || i+k >= psum.length){
                answer[i] = -1;
                continue;
            }
            answer[i] = (int)((psum[i+k] - psum[i-k] + nums[i-k]) / range);
        }

        return answer;
    }
}

---

문제링크: https://leetcode.com/problems/find-the-highest-altitude/description/

1732. Find the Highest Altitude

바이커가 여행을 하고 있다. 이 여행은 서로 다른 고도에 있는 n+1개의 point가 있다. 바이커는 고도 0인 지점인 point 0에서 출발한다.

길이가 n인 정수 배열 gain이 주어진다. gain[i]는i와 i+1 point사이의 순 altitude 차이다. 가장 큰 altitude를 리턴해라.

Ex)

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

 

제약사항

n == gain.length

1 <= n <= 100

-100 <= gain[i] <= 100

 

아이디어:

예시 자체가 prefix sum을 나타낸다. 하지만 최댓값만 리턴하면 되니까 배열에 따로 저장할 필요는 없어보인다.

sum의 최대/최소도 int로 커버 가능한 수준이다.

순회하면서 curr값을 갱신하고 그 값을 통해 max값을 갱신하자.

고지는 0부터 시작하니까 max 0으로 설정

class Solution {
    public int largestAltitude(int[] gain) {
        int curr = 0;
        int max = 0;

        for(int i = 0; i < gain.length; i++){
            curr += gain[i];
            max = Math.max(max, curr);
        }

        return max;
    }
}

---

문제링크: https://leetcode.com/problems/find-pivot-index/description/

724. Find Pivot Index

정수 배열 nums가 주어질 때, 배열의 pivot index를 계산해라.

어떤 index를 기준으로 왼쪽의 합과 오른쪽의 합이 같은 경우에 그 index를 pivot index라고 한다.

만약 왼쪽 맨 끝의 index로 따지면 left sum은 0이다. 왜냐하면 왼쪽에 index가 없기 때문이다. 오른쪽도 마찬가지다.

제일 왼쪽에 있는 pivot index를 구해라. 없다면 -1을 리턴해라.

Ex)

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

 

제약사항

1 <= nums.length <= 10^4

-1000 <= nums[i] <= 1000

 

아이디어:

index를 돌면서 각각 left sum과 right sum을 구한다면 nums.length때문에 시간제한에 걸릴 것이다.

nums[i]의 최댓값은 1000 * 10^4 = 10^7 int로 커버 가능하다.

left sum과 right sum을 빠르게 구하기 위해 prefix sum을 이용하자.

 

prefix sum을 구한다. totalSum도 구한다.

index를 돌면서 leftSum은 psum[i] - nums[i]일 테고 rightSum은 totalSum - psum[i]일 것이다. 둘이 같은지 비교.

같다면 그 Index 리턴

만약 루프를 다 돌았다면 -1 리턴

class Solution {
    public int pivotIndex(int[] nums) {
        int length = nums.length;
        int[] psum = new int[length];
        psum[0] = nums[0];
        for(int i = 1; i < length; i++){
            psum[i] = psum[i-1] + nums[i];
        }
        int min = length; // 최댓값 범위보다 크게
        for(int i = 0; i < length; i++){
            if(psum[i] - nums[i] == psum[length-1] - psum[i]){
                return i;
            }
        }
        return -1;
    }
}

---

문제링크: https://leetcode.com/problems/range-sum-query-immutable/description/

303. Range Sum Query - Immutable

정수 배열 nums가 주어질 때, 다음과 같은 타입의 복합 쿼리들을 다루자.

left와 right 사이의 nums 원소들의 합을 계산한다. left와 right 포함.

NumArray 클래스 구현:

NumArray(int[] nums) 생성자.

int sumRange(int left, int right)는 left와 right 사이의 원소들의 sum을 리턴한다. left와 right 포함.

 

Ex)

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

 

제약사항

1 <= nums.length <= 10^4

-10^5 <= nums[i] <= 10^5

0 <= left <= right <= nums.length

sumRange는 거의 10^4번 호출한다.

 

아이디어:

subArray의 합을 구해야하는데 빠르게 구해야하는 상황 => prefix sum 이용하자.

class NumArray {
    private int[] nums;
    private int[] psum;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.psum = new int[nums.length];
        psum[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            psum[i] = psum[i-1] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return psum[right] - psum[left] + nums[left];
    }
}

 

음 뭔가 nums 변수를 두지 않고 하면 좀 더 시간을 앞당길 수 있지 않을까? nums가 없다면 left-1 인덱스에 접근해야한다. left가 0이면 오류가 날 수 있다. left가 0일 때를 따로 처리하자.

class NumArray {
    private int[] psum;

    public NumArray(int[] nums) {
        this.psum = new int[nums.length];
        psum[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            psum[i] = psum[i-1] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        if (left == 0) return psum[right];
        return psum[right] - psum[left-1];
    }
}

더 빨라졌다,,!