Range Sum Query - Immutable with 2D

안녕하세요 !

 

오늘의 문제 두 개를 들고 와봤습니다.

 

하나는 Easy

https://leetcode.com/problems/range-sum-query-immutable/submissions/

Range Sum Query - Immutable - LeetCode

 

하나는 Medium 입니다.

https://leetcode.com/problems/range-sum-query-2d-immutable/

Range Sum Query 2D - Immutable - LeetCode

 

바로 갑시다 !

---

우선 Easy의 경우엔 하나의 배열이 주어지는데, 그 다음 주어지는 구간의 합을 구하는 겁니다.

 

다들 여기서 득달같이 그냥 for 문 돌려서 답을 뱉을 수도 있으실텐데, 그랬다간 시간 터져욧 !!!

제가 그랬거든요

그러면 어떻게 해야하는가?

 

바로 애시당초 앞에서 부터 합을 전부 더해온 sums 라는 배열을 만들어서 이를 이용하는 겁니다.

 

예를 들어 sums[5] = arr[5] + arr[4] + arr[3] + arr[2] + arr[1] + arr[0]이 되는거죠. 그렇다면 여러분들은 3 ~ 5 구간을 구할 땐 sums[5] - sums[2]를 해주면 됩니다 !

 

간단하쥬?

class NumArray:

    def __init__(self, nums: List[int]):
        self.sums = [0]
        for i in range(len(nums)):
            self.sums.append(nums[i] + self.sums[i])

    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j + 1] - self.sums[i]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

자 바로 다음 녀석 가봅시다.

---

다음 녀석은 배열이 주어지지만, 2D 입니다 !

 

똑같이 sum 배열을 쓰면 됩니다. 허나 이녀석은 2D 이기에 중복해서 들어가는 값을 제거를 해야합니다.

 

즉, sums[i][j] = sums[i][j] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] 의 마지막 부분 sums[i - 1][j - 1]을 빼주어야 정확한 계산이 이뤄집니다.

 

그러면 만약 구간 별로 값을 구하고 싶으면 어떻게 할까요?

 

(i1, j1) => (i2, j2) 구간까지의 합을 원하면 sums[i2][j2] - sums[i2][j1 -1] - sums[i1 -1][j2] + sums[i1 -1][j1 - 1]을 하면됩니다.

 

결국 그 범위 만큼 행렬을 빼는건데 2개를 빼다보면 중복된 부분이 있기 때문에를 다시 더해주어야합니다.

 

사실 위에 문제를 해결했다면, 아래 문제는 조금만 고민하면 푸실 수 있는 문제이실겁니다.

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        if matrix:
            self.sums = [[0 for i in range(len(matrix[0]) + 1)] for j in range(len(matrix) + 1)]
            for i in range(1, 1 + len(matrix)):
                for j in range(1, 1 + len(matrix[0])):
                    self.sums[i][j] = matrix[i - 1][j - 1]
                    self.sums[i][j] = self.sums[i][j] + self.sums[i][j-1] + self.sums[i - 1][j] - self.sums[i-1][j-1]
        else:
            self.sums = []
            
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        if self.sums:
            return self.sums[row2 + 1][col2 + 1] - self.sums[row2 + 1][col1] - self.sums[row1][col2 + 1] + self.sums[row1][col1]
        else:
            return 0


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

---

이상 Range Sum Query - Immutable with 2D였습니다. ^_^