23.08.20 Today’s Leetcode

1203. Sort Items by Groups Respecting Dependencies

i try to use a indegree and some graph theories but failed

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        d = defaultdict(list)
        indegree = [0] * n
        req = []

        for i in range(n):
            d[group[i]].append(i)
            for item in beforeItems[i]:
                indegree[item] += 1
            req.append(set(beforeItems[i]))
        
        for key in range(-1, m):
            d[key] = sorted(d[key], key=lambda x: -indegree[x])
        
        print(d)
        print(indegree)
        print(req)
        
        res = []
        cur = set()
        while len(res) < n:
            print(d)
            print(res)
            print(cur)
            group_id = -1
            for key in d.keys():
                cur_ = set(cur)
                temp = True
                for value in d[key]:
                    if req[value] - cur_:
                        temp = False
                        break
                    cur_.add(value)
                if temp:
                    group_id = key
                    cur = cur_
                    break

            res += d[group_id]
            del d[group_id]
            
            temp = []
            for value in d[-1]:
                if req[value] - cur:
                    temp.append(value)
                else:
                    res.append(value)
                    cur.add(value)
            if temp:
                d[-1] = temp
            else:
                del d[-1]


        return res

indgree로 접근하는 방식은 좋았으나, code의 구조적인 문제.

import collections
from typing import List
class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:


        def topoSort(nodes, graph, in_degree):
            queue = collections.deque([node for node in nodes if node not in in_degree])
            ans = []

            while queue:
                cur_node = queue.popleft()
                ans.append(cur_node)

                for neighbor in graph[cur_node]:
                    in_degree[neighbor] -= 1

                    if in_degree[neighbor] == 0:
                        queue.append(neighbor)

            return ans

        group_items = defaultdict(list)
        groupId = m
        for i in range(n):
            if group[i] == -1:
                group[i] = groupId
                # no groups -> set independent groupId
                groupId += 1

            group_items[group[i]].append(i)

        item_graph = defaultdict(list)
        item_indegree = defaultdict(int)

        
        for v, u_list in enumerate(beforeItems):
            for u in u_list:
                # get indegree of items that has same groupId
                if group[u] == group[v]:
                    item_graph[u].append(v)
                    item_indegree[v] += 1


        sorted_group_items = {}
        for groupId in group_items:
            # sort items within groups
            sorted_items = topoSort(group_items[groupId], item_graph, item_indegree)

            # possibility check!
            if len(sorted_items) != len(group_items[groupId]):
                return []

            sorted_group_items[groupId] = sorted_items


        group_graph = defaultdict(list)
        group_indegree = defaultdict(int)

        for v, u_list in enumerate(beforeItems):
            for u in u_list:
                if group[u] != group[v]:
                    group_graph[group[u]].append(group[v])
                    group_indegree[group[v]] += 1


        # 아하 이해함.
        groups = set(group)
        sorted_groups = topoSort(groups, group_graph, group_indegree)

        if len(groups) != len(sorted_groups):
            return []

        ans = []
        for groupId in sorted_groups:
            ans.extend(sorted_group_items[groupId])

        return ans