문제 개요
LeetCode의 2736. 최대합 쿼리는 난이도가 고난도이며, 다음 태그를 포함한다:정렬, 이산화, 트리 구조 배열 (트리형 배열).
두 개의 길이가 동일한 정수 배열 nums1과 nums2가 주어지고, 각각의 인덱스에 해당하는 요소는 짝을 이루며 하나의 쌍을 형성한다. 또한 하위 인덱스가 1부터 시작하는 2차원 배열인 queries가 제공된다.
각 쿼리 i에 대해, 조건 nums1[j] ≥ xi 및 nums2[j] ≥ yi를 만족하는 모든 인덱스 j 중에서 nums1[j] + nums2[j]의 최댓값을 찾는다. 조건을 만족하는 인덱스가 없을 경우 -1을 반환한다.
결과로 얻은 배열 answer는 각 쿼리의 결과값을 담고 있으며, answer[i]는 i번째 쿼리의 답이다.
예시 분석
예시 1:입력:
nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]출력:
[6,10,7]해설:
- 첫 번째 쿼리:
x=4, y=1 → j=0 선택 가능 (4≥4, 2≥1), 합 = 6.- 두 번째 쿼리:
x=1, y=3 → j=2 선택 가능 (1≥1, 9≥3), 합 = 10.- 세 번째 쿼리:
x=2, y=5 → j=3 선택 가능 (2≥2, 5≥5), 합 = 7.
예시 2:입력:
nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]출력:
[9,9,9]해설:
j=2는 모든 쿼리 조건을 만족하므로 항상 최대값 9를 반환.
예시 3:입력:
nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]출력:
[-1]해설: 모든 인덱스에서 최소 하나의 조건이 만족되지 않음 → 해답 없음.
핵심 접근법: 이산화 + 정렬 + 트리형 배열
기본 아이디어는 두 배열을 쌍으로 묶어 처리하고, 쿼리를 추가 정보와 함께 저장하여 순서 기반 처리를 가능하게 한다. 1. 데이터 준비:-
nums 배열을 생성하여 [nums1[i], nums2[i]] 형태로 구성.-
queries를 확장하여 원래 인덱스 정보를 유지할 수 있도록 [x, y, original_index] 형식으로 재구성.
2. 이산화:-
nums의 두 번째 값과 queries의 y 값들을 모아 유니크한 값 리스트로 만들고 정렬.- 이를 통해 원래 값들을 0부터 시작하는 인덱스로 매핑 (예:
value → index).
3. 정렬 기반 처리:-
nums와 queries 모두 첫 번째 값(즉, x) 기준으로 내림차순 정렬.- 이렇게 하면 큰
x 값을 가진 쿼리부터 처리되며, 그에 따라 만족하는 nums 쌍을 점진적으로 추가.
4. 트리형 배열 활용:- 이산화된
nums[i][1] 값을 기준으로 트리형 배열의 위치로 사용.- 이 때,
sz - map[value]로 반전된 인덱스를 사용함으로써, nums2[j] ≥ y 조건을 만족하는 후행 최댓값을 효율적으로 조회 가능.- 트리형 배열은 단일 위치에 값 업데이트와 범위 최댓값 조회를 지원하며, 시간 복잡도
O(log n)로 가능.
5. 쿼리 처리 흐름:- 현재 쿼리의
x보다 큰 nums 쌍을 전부 트리형 배열에 삽입.- 이후
y에 대응하는 이산화된 값의 반전 인덱스를 기준으로 후행 최댓값을 조회.- 결과를 원래 인덱스에 맞춰 저장.
코드 예시
class Solution {
int sz;
int[] tr;
int lowbit(int x) { return x & -x; }
void add(int a, int b) {
for (int i = a; i <= sz; i += lowbit(i))
tr[i] = Math.max(tr[i], b);
}
int query(int x) {
int ans = -1;
for (int i = x; i > 0; i -= lowbit(i))
ans = Math.max(ans, tr[i]);
return ans;
}
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.length, m = queries.length;
int[][] nums = new int[n][2];
int[][] nq = new int[m][3];
for (int i = 0; i < n; i++) nums[i] = new int[]{nums1[i], nums2[i]};
for (int i = 0; i < m; i++) nq[i] = new int[]{queries[i][0], queries[i][1], i};
Set<Integer> set = new HashSet<>();
for (int[] x : nums) set.add(x[1]);
for (int[] q : nq) set.add(q[1]);
List<Integer> list = new ArrayList<>(set);
Collections.sort(list);
sz = list.size();
Map map = new HashMap<>();
for (int i = 0; i < sz; i++) map.put(list.get(i), i);
Arrays.sort(nums, (a, b) -> b[0] - a[0]);
Arrays.sort(nq, (a, b) -> b[0] - a[0]);
tr = new int[sz + 10];
Arrays.fill(tr, -1);
int[] ans = new int[m];
int idx = 0;
for (int[] q : nq) {
int x = q[0], y = q[1], i = q[2];
while (idx < n && nums[idx][0] >= x) {
add(sz - map.get(nums[idx][1]), nums[idx][0] + nums[idx][1]);
idx++;
}
ans[i] = query(sz - map.get(y));
}
return ans;
}
}
class Solution {
public:
int sz;
vector<int> tr;
int lowbit(int x) { return x & -x; }
void add(int a, int b) {
for (int i = a; i <= sz; i += lowbit(i))
tr[i] = max(tr[i], b);
}
int query(int x) {
int ans = -1;
for (int i = x; i > 0; i -= lowbit(i))
ans = max(ans, tr[i]);
return ans;
}
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector& queries) {
int n = nums1.size(), m = queries.size();
vector nums(n, vector<int>(2));
vector nq(m, vector<int>(3));
for (int i = 0; i < n; i++) {
nums[i][0] = nums1[i]; nums[i][1] = nums2[i];
}
for (int i = 0; i < m; i++) {
nq[i][0] = queries[i][0]; nq[i][1] = queries[i][1]; nq[i][2] = i;
}
unordered_set<int> set;
for (auto& x : nums) set.insert(x[1]);
for (auto& q : nq) set.insert(q[1]);
vector<int> list(set.begin(), set.end());
sort(list.begin(), list.end());
sz = list.size();
map map;
for (int i = 0; i < sz; i++) map[list[i]] = i;
sort(nums.begin(), nums.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] > b[0];
});
sort(nq.begin(), nq.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] > b[0];
});
tr.resize(sz + 10, -1);
vector<int> ans(m);
int idx = 0;
for (auto& q : nq) {
int x = q[0], y = q[1], i = q[2];
while (idx < n && nums[idx][0] >= x) {
add(sz - map[nums[idx][1]], nums[idx][0] + nums[idx][1]);
idx++;
}
ans[i] = query(sz - map[y]);
}
return ans;
}
};
class Solution:
def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
sz = 0
tr = []
def lowbit(x): return x & -x
def add(a, b):
i = a
while i <= sz:
tr[i] = max(tr[i], b)
i += lowbit(i)
def query(x):
ans, i = -1, x
while i > 0:
ans = max(ans, tr[i])
i -= lowbit(i)
return ans
n, m = len(nums1), len(queries)
nums = [(nums1[i], nums2[i]) for i in range(n)]
nq = [(queries[i][0], queries[i][1], i) for i in range(m)]
unique_set = set()
for x in nums: unique_set.add(x[1])
for q in nq: unique_set.add(q[1])
unique_list = sorted(unique_set)
sz = len(unique_list)
mapping = {val: idx for idx, val in enumerate(unique_list)}
nums.sort(key=lambda x: x[0], reverse=True)
nq.sort(key=lambda x: x[0], reverse=True)
tr = [-1] * (sz + 10)
ans = [0] * m
idx = 0
for x, y, i in nq:
while idx < n and nums[idx][0] >= x:
add(sz - mapping[nums[idx][1]], nums[idx][0] + nums[idx][1])
idx += 1
ans[i] = query(sz - mapping[y])
return ans
function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {
let sz = 0;
let tr = [];
const lowbit = (x: number): number => x & -x;
const add = (a: number, b: number): void => {
for (let i = a; i <= sz; i += lowbit(i)) tr[i] = Math.max(tr[i], b);
};
const query = (x: number): number => {
let ans = -1;
for (let i = x; i > 0; i -= lowbit(i)) ans = Math.max(ans, tr[i]);
return ans;
};
const n = nums1.length, m = queries.length;
const nums = Array.from({ length: n }, (_, i) => [nums1[i], nums2[i]]);
const nq = Array.from({ length: m }, (_, i) => [...queries[i], i]);
const set = new Set<number>();
for (const x of nums) set.add(x[1]);
for (const q of nq) set.add(q[1]);
const list = [...set].sort((a, b) => a - b);
sz = list.length;
const mapping = new Map();
for (let i = 0; i < sz; i++) mapping.set(list[i], i);
nums.sort((a, b) => b[0] - a[0]);
nq.sort((a, b) => b[0] - a[0]);
tr = Array(sz + 10).fill(-1);
const ans = Array(m).fill(0);
let idx = 0;
for (let [x, y, i] of nq) {
while (idx < n && nums[idx][0] >= x) {
add(sz - mapping.get(nums[idx][1])!, nums[idx][0] + nums[idx][1]);
idx++;
}
ans[i] = query(sz - mapping.get(y)!);
}
return ans;
}
복잡도 분석
- 시간 복잡도:O((n + m) log(n + m))- 이산화 및 정렬 과정이 주된 비용. - 공간 복잡도:
O(n + m)- 이산화 리스트, 맵, 트리형 배열 등이 메모리 사용.
확장 고민: 3차원 편향 문제 해결 전략
이 문제는 "1차원 정렬 + 1차원 트리형 배열"로 2차원 편향 문제를 해결하는 모델을 보여준다. 3차원 편향 문제에 대한 일반적 접근은 다음과 같다: - 1차원 정렬: 가장 큰 차원 기준으로 정렬.- 2차원 병합 정렬 (Merge Sort): 중간 차원을 기준으로 분할 정복.
- 3차원 트리형 배열: 나머지 차원에 대해 빠른 최댓값 조회. 이 방식은 다차원 편향 문제를 효율적으로 해결할 수 있는 통합 프레임워크를 제공한다.