C++で身長を基準にキューを再構築するアルゴリズム

人々がランダムな順序で列に並んでいる状況を考えてみましょう。各人は整数のペア (h, k) で表されます。ここで、h はその人の身長、k は自分より前に並んでいる「身長が h 以上の人」の人数を意味します。この情報をもとに、条件を満たすようにキューを再構築するメソッドを定義するのが本記事の目的です。

例えば、入力が [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] の場合、正しい出力は [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] となります。

解法のアプローチ

この問題は、「背の高い人から順に決まった位置へ挿入していく」という貪欲法の発想で解くことができます。手順は以下の通りです。

• 次の比較戦略に基づいて、与えられた配列をソートします。
  • a[0] == b[0](身長が同じ)の場合は a[1] > b[1]、つまり k の降順で並べる
  • それ以外の場合は a[0] < b[0]、つまり身長の昇順で並べる
• 結果を格納するためのベクター ans を作成します。
• ソート済み配列の末尾(最も背が高い人)から先頭に向かってループ処理を行い、各人物 p[i] を ans の p[i][1] 番目の位置に挿入します。
• 最後に ans を返します。

なぜこの方法が機能するのか

背の高い人から順に挿入していくため、後から挿入される背の低い人は、すでに配置された人の相対的な前後関係に影響を与えません。また、同じ身長の場合に k の大きい方を先に処理することで、同じ身長同士の順序関係も正しく保たれます。

実装例

以下のC++コードで、実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> 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;
}
bool cmp(vector<int> a, vector<int> b){
    if(a[0] == b[0]) return a[1] > b[1];
    return a[0] < b[0];
}
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        sort(p.begin(), p.end(), cmp);
        vector<vector<int>> ans;
        for(int i = p.size()-1; i>=0; i--){
            ans.insert(ans.begin() + p[i][1], p[i]);
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
    print_vector(ob.reconstructQueue(v));
}

入力

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

出力

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

このように、カスタム比較関数によるソートと位置指定の挿入を組み合わせるだけで、O(n²) の計算量でキューを正しく再構築できます。シンプルでありながら強力なテクニックなので、競技プログラミングやコーディング面接でも役立つでしょう。