C++でレストランの注文一覧表（ディスプレイテーブル）を作成する方法

レストランで顧客が行った注文を表す配列 orders があるとします。各要素は orders[i] = [cust_name_i, table_num_i, food_item_i] の形式で、cust_name_i は顧客名、table_num_i はテーブル番号、food_item_i は顧客が注文した料理を表します。

このとき、レストランの「ディスプレイテーブル」を返す必要があります。ディスプレイテーブルとは、各行に「どのテーブルがどの料理を何個注文したか」を示す表のことです。1列目にはテーブル番号が入り、残りの列には料理名がアルファベット順に並びます。また、1行目はヘッダー行とし、最初のセルは「Table」、続いて料理名を記述します。

入力例と出力例

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

orders = [["Amal","3","Paratha"],["Bimal","10","Biryni"],["Amal","3","Fried Chicken"],["Raktim","5","Water"],["Raktim","5","Paratha"],["Deepak","3","Paratha"]]

この場合の出力は次のようになります。

[["Table","Biryni","Fried Chicken","Paratha","Water"],["3","0","1","2","0"],["5","0","0","1","1"],["10","1","0","0","0"]]

テーブル3ではパラータが2個、フライドチキンが1個注文されており、テーブル5ではパラータと水がそれぞれ1個ずつ、テーブル10ではビリヤニが1個注文されていることが一目でわかります。

解決のためのアルゴリズム

この問題を解くためには、以下の手順に従います。

• マップ m を定義する（キー：テーブル番号と料理名、値：注文数）

• セット names を定義する（料理名を格納し、自動的にソートされる）

• セット t を定義する（テーブル番号を格納する）

• 注文リストの各要素 it に対して以下を処理する：

  • it[1]（テーブル番号）をセット t に挿入する

  • フラグ ok = true を設定する

  • ok が false の場合は、it[2] を空白文字で分割した配列 v を作成し、v の各要素 x について m[it[1], x] を1増やし、x を names に挿入する

  • そうでない場合は、m[it[1], it[2]] を1増やし、it[2] を names に挿入する

• 2次元配列 ret を定義する

• 配列 temp を作成し、names の要素をコピーする

• temp の先頭に「Table」を挿入する

• temp を ret の末尾に追加する（これがヘッダー行になる）

• セット t の各要素 it（テーブル番号）に対して以下を処理する：

  • 配列 te を定義し、先頭にテーブル番号を挿入する

  • names の各要素 x に対して、m[it, x] の値を文字列として te の末尾に追加する

  • te を ret の末尾に追加する

• 配列 ret をソートする（ヘッダー行を除き、テーブル番号の数値順に並べる）

• ret を返す

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<string> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
    vector <string> split(string& s, char delimiter){
        vector <string> tokens;
        string token;
        istringstream tokenStream(s);
        while(getline(tokenStream, token, delimiter)){
            tokens.push_back(token);
        }
        return tokens;
    }
    static bool cmp(vector <string>& a, vector <string>& b){
        lli an = stol(a[0]);
        lli bn = stol(b[0]);
        return an < bn;
    }
    vector<vector<string>> displayTable(vector<vector<string>>& o) {
        map <string, map < string, int> >m;
        set <string> names;
        set <string> t;
        for(auto &it : o){
            t.insert(it[1]);
            bool ok = true;
            if(!ok){
                vector <string> v = split(it[2], ' ');
                for(auto& x : v){
                    m[it[1]][x]++;
                    names.insert(x);
                }
            }
            else{
                m[it[1]][it[2]]++;
                names.insert(it[2]);
            }
        }
        vector < vector <string> > ret;
        vector <string> temp(names.begin(), names.end());
        temp.insert(temp.begin(), "Table");
        ret.push_back(temp);
        for(auto& it : t){
            vector <string> te;
            te.push_back(it);
            for(auto& x : names){
                te.push_back(to_string(m[it][x]));
            }
            ret.push_back(te);
        }
        sort(ret.begin() + 1, ret.end(), cmp);
        return ret;
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{"Amal","3","Paratha"},{"Bimal","10","Biryni"},{"Amal","3","Fried Chicken"},{"Raktim","5","Water"},{"Raktim","5","Paratha"},{"Deepak","3","Paratha"}};
    print_vector(ob.displayTable(v));
}

入力

{{"Amal","3","Paratha"},{"Bimal","10","Biryni"},{"Amal","3","Fried Chicken"},{"Raktim","5","Water"},{"Raktim","5","Paratha"},{"Deepak","3","Paratha"}}

出力

[[Table, Biryni, Fried Chicken, Paratha, Water],[3, 0, 1, 2, 0],[5, 0, 0, 1, 1],[10, 1, 0, 0, 0]]

実装のポイント

このコードの重要なポイントをいくつか紹介します。

• std::map と std::set の活用： C++の map と set は要素を自動的にソートして保持するため、料理名のアルファベット順管理が容易になります。

• カスタム比較関数： テーブル番号は文字列として保存されているため、そのままソートすると辞書順になってしまいます。stol() 関数で数値に変換してから比較することで、正しく数値順にソートできます。

• ネストされたマップ構造： map<string, map<string, int>> という二重マップを使うことで、「テーブル番号 → 料理名 → 注文数」という階層的なデータを効率的に管理できます。

このアルゴリズムの計算量は、注文数を N、テーブル数を T、料理の種類数を F とすると、O(N + T×F) となります。非常に効率的な解法です。