C++で相対ランクを求める：上位3名に金・銀・銅メダルを割り当てるアルゴリズム

問題概要

N人の選手のスコアのリストが与えられ、それぞれの相対的な順位を求めます。中でも最も高いスコアを持つ上位3名には、それぞれ「Gold（金）」「Silver（銀）」「Bronze（銅）」のメダルを割り当てます。

たとえば、入力が [2,5,3,1,0] の場合、出力は [Bronze, Gold, Silver, 4, 5] となります。

解法のアプローチ

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

1. nums のサイズが 1 の場合は「Gold」を返します。
2. nums のサイズが 2 の場合は、nums[0] > nums[1] であれば「Gold, Silver」を、そうでなければ「Silver, Gold」を返します。
3. 配列 v と vec を定義します。
4. nums のすべての要素を v の末尾に追加します。
5. 配列 v をソートし、さらに逆順（降順）に並べ替えます。
6. マップ mp を定義します。
7. nums のサイズが 2 より大きい場合、次の処理を行います。
   • mp に {v[0], Gold}、{v[1], Silver}、{v[2], Bronze} を登録します。
   • i = 3 から v の末尾まで、{v[i], 順位（i + 1 の文字列表現）} を mp に登録します。
   • nums の各要素 i について、mp[nums[i]] を vec の末尾に追加します。
8. vec を返します。

アルゴリズムのポイント

この解法では、元の配列の順序を保持しながら順位を求める必要があるため、まずスコアのコピーを作成して降順にソートし、各スコアと順位（またはメダル名）の対応をマップに記録します。あとは元の配列を先頭から走査し、マップを参照することで、対応する結果を正しい位置に配置できます。全体の計算量は O(N log N) となり、ボトルネックはソート処理です。

実装例

以下のC++実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<string> findRelativeRanks(vector<int>& nums){
      if (nums.size() == 1){
         return { "Gold" };
      }
      if (nums.size() == 2){
         if (nums[0] > nums[1])
            return { "Gold", "Silver" };
         else
            return { "Silver", "Gold" };
      }
      vector<int> v;
      vector<string> vec;
      for (int i = 0; i < nums.size(); i++)
         v.push_back(nums[i]);
      sort(v.begin(), v.end());
      reverse(v.begin(), v.end());
      map<int, string> mp;
      if (nums.size() > 2) {
         mp.insert({v[0], "Gold" });
         mp.insert({v[1], "Silver" });
         mp.insert({v[2], "Bronze" });
         for (int i = 3; i < v.size(); i++) {
            mp.insert({ v[i], to_string(i + 1) });
         }
         for (int i = 0; i < nums.size(); i++)
            vec.push_back(mp[nums[i]]);
      }
      return vec;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,5,3,1,0};
   print_vector(ob.findRelativeRanks(v));
}

入力

{2,5,3,1,0}

出力

[Bronze, Gold, Silver, 4, 5]