DP 에 조금 감을 잡은거 같아서 풀어보려고 leetcode 에 검색했다가 easy 문제를 발견했다.
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Implement the NumArray class:
•
NumArray(int[] nums) Initializes the object with the integer array nums.
•
int sumRange(int i, int j) Return the sum of the elements of the nums array in the range [i, j] inclusive (i.e., sum(nums[i], nums[i + 1], ... , nums[j]))
문제가 처음엔 쉽게 느껴진 것이 그냥 arr 만들고 sum 하면 되지 않나? 하는 생각을 했다.
brute force 방식이다.
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public int sumRange(int i, int j) {
int result = 0;
for (int index = i; index <= j; index ++) {
result += nums[index];
}
return result;
}
}
Java
복사
내 위치가 여기다... 그럼 개선을 해야지ㅠㅠ
"먼저 든 생각은 sum 의 결과를 저장할 방법이 없는가?" 였다
생성자를 통해 int array 를 받고, sumRange 를 통해 i 번째 index 부터 j번째 index 까지 더한 값을 반환해야 한다. 어떻게 해야할까?
0, 5 라고 한다면 arr[0] + arr[1] + arr[2] + arr[3] + arr[4] + arr[5] 의 결과를 반환해야 한다.
하지만, 3, 5 라고 한다면 arr[3] + arr[4] + arr[5] 의 결과를 반환해야 한다.
i 와 j 에 어떠한 값이 올지 모르는데 어떻게 캐싱을 하면 좋을까?
그런데 저렇게 적고 보니 이러한 방법이 떠올랐다
•
sumRange(3, 5) 는 sumRange(0, 5) - sumRange(0, 2) 가 성립한다.
sumRange(0, 2) = arr[0] + arr[1] + arr[2] 이다.
그렇다면 0 부터 nums.length-1 까지의 합을 저장해두고, 그때그때 계산해준다면 어떨까?
생성자에 다음과 같은 로직을 추가하는 것이다
int[] sums;
public NumArray(int[] nums) {
this.sums = new int[10000]; //조건에 10^4 까지 온다는 조건이 있음
for (int i = 1; i < nums.length; i ++) {
sums[i] = sums[i-1] + nums[i];
}
}
Java
복사
sums[] 에 저장되는 값은 다음과 같다.
1.
sums[0] = nums[0]
2.
sums[1] = sums[0] + nums[1]
3.
sums[2] = sums[1] + nums[2]
4.
sums[3] = sums[2] + nums[3]
이렇게 nums.length - 1 까지 순회하며 값을 저장한다.
sumRange 는 다음과 같이 구현한다
public int sumRange(int i, int j) {
if (i == 0) return sums[j];
return sums[j] - sums[i-1];
}
Java
복사
return sums[j] - sums[i-1]; 이 코드가 sumRange(0, 5) - sumRange(0, 2) 이러한 역할을 수행하는 것이다.
결과는
생성할 때 빈 배열을 넣는 경우가 있다. 그러면 생성자를 수정하여 다음과 같이 변경한다
class NumArray {
private int[] sums;
public NumArray(int[] nums) {
sums = new int[10000];
// 빈배열이 input 인 경우 대응
if (nums.length == 0) {
return;
}
sums[0] = nums[0];
for (int i = 1; i < nums.length ; i ++) {
sums[i] = sums[i-1] + nums[i];
}
}
public int sumRange(int i, int j) {
if (i == 0) return sums[j];
return sums[j] - sums[i-1];
}
}
Java
복사
내 풀이의 runtime 시간이 다음과 같다.
헤헷ㅋ
solution 보니 마지막 해법이 내가 푼 풀이랑 똑같다
