Algorithm問題を解く 9 - 複数タグのマッチ判定

問題

You are building a social networking site where each user specifies a set of attributes. You would like to pair each user with another unpaired user that specifies exactly the same set of attributes. Specifically, you are given a sequence of users where each user has a unique key, say a 32-bit integer and a set of attributes specified as a set of strings. As soon as you read a user, you should pair it with another previously read user with identical attributes who is currently unpaired, if such a user exists. If the user cannot be paired, you should keep him in the unpaired set.

(Algorithms for interviewsより引用)

ヒント

文字列の一致でハッシュを使うのは，原則的にはご法度である．アナグラムのケースがあった場合プログラムは誤作動してしまう．

解答

#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>
using namespace std;

class User {
private:
 int id;
 list<std::string> attrs;
 list<int> matchedIds;
 const std::string GetFullTag();
public:
 User() {}
 User(int paramId,list<std::string>& paramAttr) : id(paramId),attrs(paramAttr) {};
 virtual ~User() {};
 bool match(User& user);
};

const std::string User::GetFullTag() {

 string s = "";
 attrs.sort();
 list<std::string>::iterator iter;
 for(iter = attrs.begin();iter != attrs.end();iter++) {
  s.append( *iter );
 }
 return s;

}

bool User::match(User& user) {

 if( std::find(matchedIds.begin(), matchedIds.end(), user.id) == matchedIds.end() ) {
  
  if( GetFullTag() == user.GetFullTag() ) {
   matchedIds.push_back(user.id);
   return true;
  }
  else
   return false;

  return false;

 }
 else {
  // already matching
  cout << "already in your list!!" << endl;
  return true;
 }
 return true;
}

int main() {
 
 list<string> my;
 my.push_back("C++");
 my.push_back("Java");
 User s( 10, my );
 list<string> you;
 you.push_back("Java");
 you.push_back("C++");
 User u( 20, you );
 cout << "you and me - " << s.match( u ) << endl;
 list<string> t;
 t.push_back("C++");
 t.push_back("Java");
 User th( 30, t );
 cout << "someone and me - " << s.match( th ) << endl;
 list<string> b;
 b.push_back("Python");
 b.push_back("Java");
 User br( 40, b );
 cout << "brother and me - " << s.match( br ) << endl;

 return 0;
}