정수 목록으로 구축할 수 있는 데이터 구조를 개발하고 효율적인 방법으로 필요할 때마다 인덱스 i에서 인덱스 j-1까지 요소의 합을 찾는 함수가 있다고 가정합니다. 두 가지 기능이 있습니다.
- 정수 배열로 새 인스턴스를 생성하는 생성자입니다.
- get_sum(i, j)은 시작 인덱스 i와 끝 인덱스 j-1부터 배열 요소의 정수 합계를 반환합니다.
따라서 입력이 array =[5,2,3,6,4,7,8,9,3,2]와 같으면 obj 개체를 구성하고 obj.get_sum(1,5) 및 obj 함수를 호출합니다. get_sum(4,8), 출력은 각각 15와 28이 됩니다. 첫 번째 범위 요소가 [2,3,6,4]이므로 합계는 15이고 두 번째 범위 요소는 [4,7,8,9]이므로 합계는 28입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 생성자를 정의합니다. 배열이 필요합니다.
- sums :=이것은 목록이며 처음에는 0을 삽입합니다.
- 배열의 각 x에 대해 다음을 수행합니다.
- 합계 끝에 (x + (합계의 마지막 항목)) 삽입
- get_sum() 함수를 정의합니다. i, j
- 반환 합계[j] - 합계[i]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class RangeSum: def __init__(self, array): self.sums = [0] for x in array: self.sums.append(x + self.sums[-1]) def get_sum(self, i, j): return self.sums[j] - self.sums[i] array = [5,2,3,6,4,7,8,9,3,2] obj = RangeSum(array) print(obj.get_sum(1,5)) print(obj.get_sum(4,8))
입력
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
출력
15 28