TopCoder Inv 2001 Semi A+B - MatchMaker

資訊

路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ MatchMaker
分數：250

題目

程式介面

Class Name: MatchMaker
Method Name: getBestMatches
Paramaters: String[], String, int
Returns: String[]
Method signature:
String[] getBestMatches(String[] members, String currentUser, int sf);

說明

線上交友網站需要透過程式來自動找出條件匹配的對象，會員會先輸入一些資料做為依據，當會員要求配對時，程式會回傳一個符合的對象清單，對象的符合項目必須大於等於設定的相似度 (similarity factor)。現在程式會先輸入會員資料、目前會員和相似度，會員資料如下格式：

1	{名稱} {性別} {對象性別} {資料1} {資料2} ...

例如

1	BETTY F M A A C C

名稱：表示會員的名稱。
性別：表示會員的性別。
對象性別：感興趣的性別。
資料：表示會員針對不同問題回答的選項，資料1 表示第一個問題的回答，資料2 表示第二個的回答，以此類推。

目前會員表示現在送出配對要求的人，而結果會回傳符合的會員名稱陣列，並依據以下規則回傳：

目標對象的性別必須與目前會員的對象性別一致。
目標對象的資料選項與目前會員一致的項目數必須大於等於輸入的相似度。
承上，回傳的排序必須依據符合項目數遞減排序。
承上，符合的項目數相同時，排序必須與輸入的會員資料順序一致。
目前會員不可出現在回傳結果中。

系統保證輸入

會員資料陣列：會員資料陣列的長度範圍為 1-50。
會員資料：7-44 個字元。
名稱：1-20 個字元 [A-Z]。
性別：M 或 F。
對象性別：M 或 F。
資料：1 個字元 [A-D]。
每筆會員資料的資料數一致。
名稱不會重複。
目前會員：1-20 個字元 [A-Z]，且在會員資料陣列中。
相似度：1-10 的整數，且小於等於資料數。

範例

假設會員資料輸入：
{"BETTY F M A A C C",
 "TOM M F A D C A",
 "SUE F M D D D D",
 "ELLEN F M A A C A",
 "JOE M F A A C A",
 "ED M F A D D A",
 "SALLY F M C D A B",
 "MARGE F M A A C C"}

輸入：currentUser="BETTY", sf=2
輸出：{"JOE","TOM"}
註：TOM 符合 2 項，JOE 符合 3 項

輸入：currentUser="JOE" and sf=1
輸出：{"ELLEN","BETTY","MARGE"}

輸入：currentUser="MARGE" and sf=4
輸出：{}

解法

這題是很簡單的條件判斷比對，篩選出符合的使用者，只有最後結果的排序要注意；依據規則的說明，表示必須使用 Stable 的方式，在 C# 的 List 內建的 Sort 是 Unstable，所以要另外實作排序，這邊簡單的利用 Insertion Sort 來達到排序結果。

語法

採用較易理解的寫法，效能並非最好

using System;
using System;
using System.Collections.Generic;
using System.Text;

namespace MatchMaker
{
    class MatchMaker
    {
        public string[] getBestMatches(string[] members, string currentUser, int sf)
        {
            Dictionary<string, Member> memberDic = ParseMembers(members);
            Dictionary<string, int> scoreDic = new Dictionary<string, int>();
            Member currentMember = memberDic[currentUser];

            List<string> result = new List<string>();
            foreach (Member member in memberDic.Values)
            {
                if (member.Name == currentUser || currentMember.TargetGender != member.Gender)
                    continue;

                int score = 0;
                for (int i = 0; i < currentMember.Answers.Length; ++i)
                    if (member.Answers[i] == currentMember.Answers[i])
                        ++score;

                if (score < sf)
                    continue;

                int index = 0;
                while (index < result.Count)
                {
                    if (scoreDic[result[index]] < score)
                        break;
                    ++index;
                }
                result.Insert(index, member.Name);
                scoreDic[member.Name] = score;
            }

            return result.ToArray();
        }

        private Dictionary<string, Member> ParseMembers(string[] members)
        {
            Dictionary<string, Member> dic = new Dictionary<string, Member>();
            foreach (string line in members)
            {
                string[] parts = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                Member member = new Member();
                member.Name = parts[0];
                member.Gender = parts[1];
                member.TargetGender = parts[2];
                member.Answers = new string[parts.Length - 3];

                for (int i = 3, j = 0; i < parts.Length; ++i, ++j)
                    member.Answers[j] = parts[i];

                dic[member.Name] = member;
            }
            return dic;
        }

        class Member
        {
            public string Name { get; set; }
            public string Gender { get; set; }
            public string TargetGender { get; set; }
            public string[] Answers { get; set; }
        }
    }
}