넘치게 채우기
[LeetCode] 2070. Most Beautiful Item for Each Query 본문
leetcode - Most Beautiful Item for Each Query
문제 유형: 정렬, 이진 탐색
문제 난이도: Medium
문제
You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively.
You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.
Return an array answer of the same length as queries where answer[j] is the answer to the jth query.
items[i] = [price, beauty]가 있다.
queries[i]의 쿼리는 queries[i]의 값을 price로 했을 때 가능한 최대의 beauty로 값을 정한다.
결과가 없으면, 0이 답이다.
answer[j] = j번째 쿼리의 결과를 답에 담은거로 해서 answer배열을 반환하시오.
풀이
unique한 price별 최대 beauty를 저장하는 newItems를 만들자.
newItems에는 items를 정렬해서 각 price별로 최대 beauty를 갖는 요소들만 저장시킨다.
newItems도 정렬된채로 저장한다.
그리고, 더 저렴한데 더 beauty가 높다면, 그 더 높은 price들의 최대 beauty도 업데이트해놓는다.
query별로 꺼내서 newItems에서 이진탐색하여 최대 beauty를 얻어 정답 배열에 저장한다.
코드
C++
#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
class Solution {
public:
int search(vector<vector<int>>& newItems, int target) {
int left = 0, right = newItems.size()-1;
while(left <= right) {
int mid = (left+right)/2;
if(newItems[mid][0] == target) return mid;
if(newItems[mid][0] < target) {
left = mid+1;
} else {
right = mid-1;
}
}
return left-1;
}
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
sort(items.begin(), items.end());
vector<vector<int>> newItems;
newItems.emplace_back(items[0]);
int n = items.size();
int m = queries.size();
int j = 0;
for(int i = 1; i < n; ++i) {
if(newItems[j][0] != items[i][0]) {
newItems.emplace_back(items[i]);
j++;
} else {
newItems[j][1] = items[i][1];
}
}
for(int i = 1; i < j+1; ++i) {
newItems[i][1] = max(newItems[i][1], newItems[i-1][1]);
}
vector<int> ans(m, 0);
for(int i = 0; i < m; ++i) {
int idx = search(newItems, queries[i]);
if(idx >= 0) ans[i] = newItems[idx][1];
}
return ans;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 2064. Minimized Maximum of Products Distributed to Any Store (0) | 2024.11.14 |
---|---|
[LeetCode] 2563. Count the Number of Fair Pairs (0) | 2024.11.13 |
[LeetCode] 2601. Prime Subtraction Operation (0) | 2024.11.11 |
[LeetCode] 3097. Shortest Subarray With OR at Least K II (0) | 2024.11.10 |
[LeetCode] 3133. Minimum Array End (0) | 2024.11.09 |