728x90
반응형
주어진 배열에서 특정 범위의 합을 계산하는 문제입니다. 주어진 배열은 변경되지 않으며 여러 번 쿼리를 수행할 수 있어야 합니다. 이 문제를 해결하기 위해 NumArray 클래스를 구현하는 것이 목표입니다.
다음은 문제의 자세한 설명입니다:
문제 설명:
불변 (immutable) 배열 nums가 주어집니다. NumArray 클래스를 구현하여 다음 두 가지 메서드를 제공하세요:
NumArray(int[] nums): 배열 nums를 입력으로 받아 초기화합니다.
int SumRange(int left, int right): left에서 right까지 (양 끝 포함) 범위 내의 원소의 합을 반환합니다.
예시:
만약 nums = [1, 2, 3, 4, 5]로 초기화된다면, 다음과 같이 NumArray 클래스를 사용할 수 있습니다:
NumArray numArray = new NumArray(nums);
int sum1 = numArray.SumRange(1, 3); // sum1 = 2 + 3 + 4 = 9
int sum2 = numArray.SumRange(0, 2); // sum2 = 1 + 2 + 3 = 6
노트:
배열 nums는 불변하며, 배열이 변경되지 않는 상황에서 여러 범위 합을 계산해야 합니다.
NumArray 클래스의 SumRange 메서드는 여러 범위에 대한 합을 효율적으로 계산해야 합니다.
이 문제의 핵심은 초기화 단계에서 미리 각 위치까지의 누적 합 (prefix sum)을 계산하고, 쿼리 수행 시 이 정보를 활용하여 범위 합을 효율적으로 계산하는 것입니다.
728x90
반응형
'Leetcode' 카테고리의 다른 글
414. Third Maximum Number (0) | 2023.11.01 |
---|---|
283. Move Zeroes (0) | 2023.10.31 |
94. Binary Tree Inorder Traversal (0) | 2023.10.30 |
83. Remove Duplicates from Sorted List (0) | 2023.10.29 |
219. Contains Duplicate II (0) | 2023.10.28 |