Leetcode 1125. Smallest Sufficient Team

https://leetcode.com/problems/smallest-sufficient-team/description/

Smallest Sufficient Team - LeetCode

문제

프로젝트를 하기위해 필요한 기술이 나열되어있는 배열 req_skills와 배열 people이 존재하다. i번쨰 사람이 가지고 있는 기술은 people[i]에 배열로 존재한다.

 

프로젝트에 필요한 기술을 충족시키기 위해 한명이라도 나열된 기술에 대한 기술을 가지고 있어야 한다. 문제에는 각 사람에 대해서 인덱스를 이용해 표시하고 있다.

 

예를 들어 team = [0, 1, 3] 이 존재한다면 people[0]는 0번 사람이 가지고 있는 기술 people[1]은 1번 사람이 가지고 있는 기술 people[3]은 3번 사람이 가지고 있는 기술을 말한다.

 

위의 조건을 참고하여 최소한의 사람을 이용해 req_skills을 만족하는 사람의 조합을 구하여 반환하라. 정답의 순서는 상관없이 그냥 반환하면 된다.

 

코드

from itertools import combinations

class Solution:

    def smallestSufficientTeam(self, req_skills: list[str], people: list[list[str]]) -> list[int]:

        m = {}

        for i, skill in enumerate(req_skills):

            m[skill] = 2 ** i

        target = 2 ** (i + 1) - 1

        mm = []

        # make to binary format

        for p in people:

            a = 0

            for s in p:

                a = a | m[s]

            mm.append(a)

        fmm = list(filter(lambda x: x, mm))

        def sumBit(nums):

            result = 0

            for n in nums:

                result = result | n

            return result

        def find(q, level):

            if level > len(fmm):

                return

            combs = combinations(fmm, level)

            for comb in combs:

                if sumBit(comb) == target:

                    return comb

            return find(q, level + 1)

        a = find(fmm, 1)

        return list(map(lambda x: mm.index(x), a))

---

라이브러리를 안쓰고 싶었는데.. 많은 시간을 쓰다보니 어쩔 수 없이 쓰게 되었다. 문제에서 bitmask를 사용해 풀면 된다고 하길래 관련 개념을 접하고 내 나름대로 아 이렇게 하면 되겠다 라고 했으나 결과는 참담했다.

저기 끝에 ... 위치한 나의 코드..