You are given a list dishes, where each element consists of a list of strings beginning with the name of the dish, followed by all the ingredients used in preparing it. You want to group the dishes by ingredients, so that for each ingredient you'll be able to find all the dishes that contain it (if there are at least 2 such dishes).

Return an array where each element is a list beginning with the ingredient name, followed by the names of all the dishes that contain this ingredient. The dishes inside each list should be sorted lexicographically, and the result array should be sorted lexicographically by the names of the ingredients.

Example

• Forthe output should be

    dishes = [["Salad", "Tomato", "Cucumber", "Salad", "Sauce"],
              ["Pizza", "Tomato", "Sausage", "Sauce", "Dough"],
              ["Quesadilla", "Chicken", "Cheese", "Sauce"],
              ["Sandwich", "Salad", "Bread", "Tomato", "Cheese"]]
  
  

    solution(dishes) = [["Cheese", "Quesadilla", "Sandwich"],
                        ["Salad", "Salad", "Sandwich"],
                        ["Sauce", "Pizza", "Quesadilla", "Salad"],
                        ["Tomato", "Pizza", "Salad", "Sandwich"]]
  
  

• Forthe output should be

    dishes = [["Pasta", "Tomato Sauce", "Onions", "Garlic"],
              ["Chicken Curry", "Chicken", "Curry Sauce"],
              ["Fried Rice", "Rice", "Onions", "Nuts"],
              ["Salad", "Spinach", "Nuts"],
              ["Sandwich", "Cheese", "Bread"],
              ["Quesadilla", "Chicken", "Cheese"]]
  
  

    solution(dishes) = [["Cheese", "Quesadilla", "Sandwich"],
                        ["Chicken", "Chicken Curry", "Quesadilla"],
                        ["Nuts", "Fried Rice", "Salad"],
                        ["Onions", "Fried Rice", "Pasta"]]
  
  

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.array.string dishes

  An array of dishes, where dishes[i] for each valid i contains information about the ith dish: dishes[i][0] is the name of the dish, and all the elements after it are the ingredients of that dish. Both the dish name and the ingredient names consist of English letters and spaces. It is guaranteed that all dish names are different. It is also guaranteed that the ingredient names for any one dish are also pairwise distinct.

  Guaranteed constraints:

  1 ≤ dishes.length ≤ 500,

  2 ≤ dishes[i].length ≤ 10,

  1 ≤ dishes[i][j].length ≤ 50.

• [output] array.array.string

  The array containing the grouped dishes.

풀이

String[][] solution(String[][] dishes) {
    // 사전순 정렬을 위한 자료구조
    TreeMap <String, TreeSet <String>> map = new TreeMap<>();
    
    for (String [] arr : dishes) {
        // 요리 이름은 0 인덱스 위치
        String dish = arr[0];
        
        // 재료 : [요리1, 요리2, ...]
        for (int i = 1; i < arr.length; i ++) {
            String ingre = arr[i];
            
            if (!map.containsKey(ingre)) {
                TreeSet <String> set = new TreeSet <String> ();
                set.add(dish);
                map.put(ingre, set);
            } else {
                TreeSet <String> set = map.get(ingre);
                set.add(dish);
                map.put(ingre, set);
            }
        }
    }
    
    // 가변형 자료구조
    LinkedList <String []> buffer = new LinkedList<>();
    
    for (String s : map.keySet()) {
        // 재료에 두 가지 이상 요리가 존재
        if (map.get(s).size() > 1) {
            String [] buff = new String [map.get(s).size() + 1];
            int idx = 1;
            buff[0] = s;
            
            for (String _s : map.get(s)) {
                buff[idx ++] = _s;
            }
            
            buffer.add(buff);
        }
    }
    
    String [][] result = new String [buffer.size()][];
    
    for (int i = 0; i < result.length; i ++) {
        result[i] = buffer.get(i);
    }
    
    return result;
}