문제 링크

내 코드

2번의 Wrong Answer, 1번의 TLE

• 굳이 offline query까지 갈 필요 없었네..
  • Hint 보고 생각난 게 이것 뿐.. (How can we use the answer to a query for other queries?)

• offline query
• 72ms, 102.2MB

using pii = pair<int, int>;
class Solution {
public:
	vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {

		vector<pii> qp(queries.size(), make_pair(0, 0));
		for (int s{}, e{ static_cast<int>(queries.size()) }; s < e; ++s) {
			qp[s].first = queries[s];
			qp[s].second = s;
		}

		sort(begin(qp), end(qp), [](const pii& p1, const pii& p2) {
			if (p1.first == p2.first) return p1.second < p2.second;
			return p1.first < p2.first;
		});
		vector<int> answer(queries.size(), 0);

		// map<int, int, greater<int>> m;
		map<int, int> m;
		for (auto& item : items) {
			int price = item[0], beauty = item[1]; // structured binding 사용법    
			if (m.count(price)) {
				if (m[price] < beauty) m[price] = beauty;
			}
			else {
				m.emplace(price, beauty);
			}
		}

		vector<pii> mp(begin(m), end(m));

		auto it = begin(mp);
		int i{};
		for (; i < static_cast<int>(qp.size()); ++i) {
			if (it->first <= qp[i].first) break;
		}
		int now = it->second;
		 
		for (; i < static_cast<int>(qp.size()); ++i) { // auto[query, index] : qp) {
			auto[query, index] = qp[i];
			while (it!=end(mp) && (it + 1) != end(mp) && (it + 1)->first <= query) {
				now = max(now, (it + 1)->second);
				++it;
			}
			answer[index] = now;
		}

		return answer;
	}
};

Solution

Approach 1: Sorting Items + Binary Search

• 39ms, 91.49MB
• Complexity
  • Let M be the size of items and let N be the size of queries.
  • Time Complexity: $O( (M + N) \cdot \log M)$
  • Space Complexity: $O(S_M)$
    • C++: sort() $\Rightarrow$ $O(\log M)$

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items,
                              vector<int>& queries) {
        vector<int> ans(queries.size());

        // Sort and store max beauty
        sort(items.begin(), items.end(),
             [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });

        int maxBeauty = items[0][1];
        for (int i = 0; i < items.size(); i++) {
            maxBeauty = max(maxBeauty, items[i][1]);
            items[i][1] = maxBeauty;
        }

        for (int i = 0; i < queries.size(); i++) {
            // answer i-th query
            ans[i] = binarySearch(items, queries[i]);
        }

        return ans;
    }

    int binarySearch(vector<vector<int>>& items, int targetPrice) {
        int left = 0;
        int right = items.size() - 1;
        int maxBeauty = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (items[mid][0] > targetPrice) {
                right = mid - 1;
            } else {
                // Found viable price. Keep moving to right
                maxBeauty = max(maxBeauty, items[mid][1]);
                left = mid + 1;
            }
        }
        return maxBeauty;
    }
};

Approach 2: Sorting Items + Sorting Queries

• 61ms, 99.08MB
• Complexity
  • Let M be the size of items and let N be the size of queries.
  • Time Complexity: $O( M \cdot \log M + N \cdot \log N)$
  • Space Complexity: $O(S_M + S_N)$
    • C++: sort() $\Rightarrow$ $O(\log M)$
    • Because we run this algorithm on both items and queries, the total space complexity would be $O(S_M + S_N)$.

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items,
                              vector<int>& queries) {
        vector<int> ans(queries.size());
        // sort both items and queries in ascending order
        sort(items.begin(), items.end(),
             [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });

        vector<vector<int>> queriesWithIndices(queries.size(), vector<int>(2));

        for (int i = 0; i < queries.size(); i++) {
            queriesWithIndices[i][0] = queries[i];
            queriesWithIndices[i][1] = i;
        }

        sort(queriesWithIndices.begin(), queriesWithIndices.end(),
             [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });

        int itemIndex = 0;
        int maxBeauty = 0;

        for (int i = 0; i < queries.size(); i++) {
            int query = queriesWithIndices[i][0];
            int originalIndex = queriesWithIndices[i][1];

            while (itemIndex < items.size() && items[itemIndex][0] <= query) {
                maxBeauty = max(maxBeauty, items[itemIndex][1]);
                itemIndex++;
            }

            ans[originalIndex] = maxBeauty;
        }
        return ans;
    }
};