Skip to Content
CoursesCSC122โปรแกรมจับคู่ความชอบ

โปรแกรมจับคู่ความชอบ

โจทย์

Cupid aims to match people based on their shared interests. Given a list of N individuals and their interests, write a program that finds the most compatible match for each person using the following criteria, in order of priority:

  1. Two people with the highest number of common interests form the strongest bond. However, if a person has no common interests with anyone, they remain unmatched and should be assigned “Forever Alone.”
  2. If multiple potential matches have the same compatibility score, select the one whose name comes first in alphabetical order.
  3. Some individuals may refuse to be paired with certain people due to past relationships. In such cases, the next best match should be considered.
  4. Each person is paired with exactly one other person. If no valid match is found, return “Forever Alone” for that individual.

Hint: retainAll() method keeps only the common elements between two collections and removes the rest.

List<String> set1 = new ArrayList<> ("apple", "banana", "cherry");
List<String> set2 = new ArrayList<>("banana", "cherry", "date");
 
set1.retainAll(set2); // Keeps only common elements: "banana" and "cherry"
System.out.println(set1); // Output: [banana, cherry]

Input:

  1. N for number of people
  2. A list of N people, each with
    • A name
    • A list of people they refuse to be paired with. Enter -1 to proceed to the next section.
    • A list of interests. Enter -1 to indicate the end of the list and proceed to the next person.

Output:

  • A list of names representing the most compatible match for each person.
InputOutput
4
Alice
Charlie -1
music movies reading -1
Bob
-1
sports music movies -1
Charlie
Alice -1
reading travel sports -1
David
-1
music movies reading -1		Alice David
Bob Alice
Charlie Bob
David Alice

โค้ด

import java.util.*;
 
public class Program {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int numPeople = scanner.nextInt();
        List<String> names = new ArrayList<>();
        List<List<String>> dislikes = new ArrayList<>();
        List<List<String>> hobbies = new ArrayList<>();
 
        for (int i = 0; i < numPeople; i++) {
            String name = scanner.next();
            names.add(name);
 
            dislikes.add(readList(scanner));
            hobbies.add(readList(scanner));
        }
 
        List<String> matches = findMatches(names, dislikes, hobbies);
 
        for (int i = 0; i < numPeople; i++) {
            System.out.println(names.get(i) + " " + matches.get(i));
        }
    }
 
    private static List<String> findMatches(List<String> names, List<List<String>> dislikes, List<List<String>> hobbies) {
        int numPeople = names.size();
        List<String> matches = new ArrayList<>();
 
        for (int i = 0; i < numPeople; i++) {
            String bestMatch = "Forever Alone";
            int maxCommonHobbies = 0;
            int bestIndex = -1;
 
            for (int j = 0; j < numPeople; j++) {
                if (i == j || dislikes.get(i).contains(names.get(j)) || dislikes.get(j).contains(names.get(i))) {
                    continue;
                }
 
                List<String> commonHobbies = new ArrayList<>(hobbies.get(i));
                commonHobbies.retainAll(hobbies.get(j));
                int commonCount = commonHobbies.size();
 
                if (commonCount > maxCommonHobbies) {
                    maxCommonHobbies = commonCount;
                    bestMatch = names.get(j);
                    bestIndex = j;
                } else if (commonCount == maxCommonHobbies && bestIndex != -1 && names.get(j).compareToIgnoreCase(names.get(bestIndex)) < 0) {
                    bestMatch = names.get(j);
                    bestIndex = j;
                }
            }
            matches.add(bestMatch);
        }
 
        return matches;
    }
 
    private static List<String> readList(Scanner scanner) {
        List<String> list = new ArrayList<>();
        while (true) {
            String input = scanner.next();
            if (input.equals("-1")) break;
            list.add(input);
        }
        return list;
    }
}

คำอธิบาย

ปรับปรุงล่าสุด