C++における無効なトランザクションの検出方法

問題の概要

いくつかの取引（トランザクション）が与えられているとします。ある取引は、以下のいずれかの条件を満たす場合に「無効である可能性」があるとみなされます。

• 取引金額が1,000ドルを超えている
• 同じ名前による別の取引が、異なる都市で60分以内（60分ちょうども含む）に行われている

各取引文字列transactions[i]はカンマ区切りの値で構成されており、それぞれ「名前」「時間（分単位）」「金額」「都市」を表しています。取引のリストが与えられたとき、無効である可能性のある取引だけを抽出して返すのが目標です。たとえば、入力が ["alice,20,800,mtv", "bob,50,1200,mtv"] の場合、bobの取引は金額が1,200ドルで1,000ドルを超えているため無効と判断され、出力は ["bob,50,1200,mtv"] となります。

解決のための手順

この問題は、以下のアルゴリズムで解くことができます。

• 結果を格納するためのセット s と、名前ごとに取引を管理するためのマップ m を定義します。
• i を 0 から t のサイズ - 1 までループします。
  • x := t[i]
  • temp := 文字列 x を解析して生成したノード
  • j を 0 から m[tempの名前] のサイズまでループします。
    • y := m[tempの名前][j]
    • yの都市がtempの都市と異なり、かつ |yの時間 − tempの時間| ≤ 60 である場合
      • ノード y を文字列形式でセット s に挿入し、さらに x も s に挿入します。
  • tempの金額が 1000 より大きい場合は、x を s に挿入します。
  • temp を m[tempの名前] に追加します。
• 最後に、セット s の要素を返します。

セットを使用することで、同一の取引が重複して結果に含まれるのを防ぐことができるのがポイントです。

実装例（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 Node{
   public:
   string name;
   string city;
   int time;
   int amount;
};
class Solution {
   public:
   Node getNode(string s){
      string temp = "";
      Node ret;
      int cnt = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == ','){
            if(cnt == 0){
               ret.name = temp;
            }
            else if(cnt == 1){
               ret.time = stoi(temp);
            }
            else if(cnt == 2){
               ret.amount = stoi(temp);
            } else {
               ret.city = temp;
            }
            cnt++;
            temp = "";
            continue;
         }
         temp += s[i];
      }
      ret.city = temp;
      return ret;
   }
   vector<string> invalidTransactions(vector<string>& t) {
      set <string >s;
      map <string ,vector < Node >> m;
      for(int i = 0; i < t.size(); i++){
         string x = t[i];
         Node temp = getNode(x);
         for(int j = 0; j < m[temp.name].size(); j++){
            Node y = m[temp.name][j];
            if(y.city != temp.city && abs(y.time - temp.time) <= 60){
               s.insert(y.name + "," + to_string(y.time) + "," + to_string(y.amount) + "," + y.city);
               s.insert(x);
            }
         }
         if(temp.amount > 1000){
            s.insert(x);
         }
         m[temp.name].push_back(temp);
      }
      vector <string> ret(s.begin(), s.end());
      return ret;
   }
};
main(){
   vector<string> v1 = {"alice,20,800,mtv","bob,50,1200,mtv"};
   Solution ob;
   print_vector(ob.invalidTransactions(v1));
}

コードのポイント

getNode関数では、カンマ区切りの文字列を1文字ずつ走査しながら、名前・時間・金額・都市の4つのフィールドに分解してNode構造体に格納しています。invalidTransactions関数では、各取引について同じ名前の過去の取引と照合し、都市が異なり時間差が60分以内であれば両方の取引を無効候補としてセットに登録します。その後、金額が1,000ドルを超える取引も登録し、最終的にセットの中身をベクトルとして返します。

入力

["alice,20,800,mtv","bob,50,1200,mtv"]

出力

[bob,50,1200,mtv]