C++でビーガン対応・価格・距離の条件からレストランをフィルタリングする方法

レストランの情報が配列として与えられます。各要素 restaurants[i] は [id, 評価(レーティング), ビーガン対応, 価格, 距離] という形式を持っています。この中から、次の3つのフィルタ条件を使ってレストランを絞り込みます。

• ビーガン対応フィルタ:true の場合は、ビーガン対応フラグが 1 のレストランのみを対象とします。false の場合は、すべてのレストランを含めることができます。
• 最大価格(maxPrice)フィルタ:価格がこの値以下のレストランのみを考慮します。
• 最大距離(maxDistance)フィルタ:距離がこの値以下のレストランのみを考慮します。

フィルタリング後のレストランIDの配列を求めます。並び順は評価の高い順(降順)とし、評価が同じ場合は ID の降順で並べます。なお、簡単化のため、ビーガン対応フラグは true のとき 1、false のとき 0 を取るものとします。

入力例と出力例

たとえば、入力が次のような場合を考えてみましょう。

[[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]]
veganFriendly = 1、maxPrice = 50、maxDistance = 10

このときの出力は [3,1,5] になります。各レストランの詳細は次の通りです。

• レストラン1:id=1、評価=4、ビーガン対応=1、価格=40、距離=10
• レストラン2:id=2、評価=8、ビーガン対応=0、価格=50、距離=5
• レストラン3:id=3、評価=8、ビーガン対応=1、価格=30、距離=4
• レストラン4:id=4、評価=10、ビーガン対応=0、価格=10、距離=3
• レストラン5:id=5、評価=1、ビーガン対応=1、価格=15、距離=1

veganFriendly = 1、maxPrice = 50、maxDistance = 10 の条件でフィルタリングすると、条件を満たすのはレストラン3、レストラン1、レストラン5の3件です。これらを評価の降順に並べると [3, 1, 5] となります。

解き方のアルゴリズム

この問題は、以下の手順で解くことができます。

1. 一時的な配列 temp を定義します。n はレストラン配列のサイズです。
2. i を 0 から n−1 まで繰り返します。
   • vf = 0 または r[i][2] = vf を満たし、かつ r[i][3] ≤ mp かつ r[i][4] ≤ md である場合、[r[i][0], r[i][1]] を temp に追加します。
3. temp 内のレストランを評価に基づいて降順にソートします。
4. 結果格納用の配列 ret を作成します。
5. i を 0 から temp のサイズまで繰り返し、temp[i][0](レストランID)を ret に挿入します。
6. ret を返します。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   static bool cmp(vector <int> a, vector <int> b){
      if(b[1] != a[1])return a[1] > b[1];
      return a[0] > b[0];
   }
   vector<int>filterRestaurants(vector<vector<int>>& r, int vf, int mp, int md) {
      vector < vector <int> > temp;
      int n = r.size();
      for(int i = 0; i < n; i++){
         if((vf == 0 || r[i][2] == vf) && r[i][3] <= mp && r[i][4] <= md){
            temp.push_back({r[i][0], r[i][1]});
         }
      }
      sort(temp.begin(), temp.end(), cmp);
      vector <int> ret;
      for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i][0]);
         return ret;
   }
};
main(){
   vector<vector<int>> v = {{1,4,1,40,10},{2,8,0,50,5},{3,8,1,30,4},{4,10,0,10,3},{5,1,1,15,1}};
   Solution ob;
   print_vector(ob.filterRestaurants(v, 1, 50, 10));
}

入力

[[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]]
1
50
10

出力

[3,1,5]