[LeetCode] 2070. Most Beautiful Item for Each Query

https://leetcode.com/problems/most-beautiful-item-for-each-query/description/?envType=daily-question&envId=2024-11-12

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;
    }
};