프로젝트에 req_skills라는 필수 기술 목록과 사람 목록이 있다고 가정합니다. 여기 i-th people people[i]에는 그 사람이 가진 기술 목록이 포함되어 있습니다.
이제 충분한 팀이 req_skills의 모든 필수 기술에 대해 해당 기술을 가진 팀에 한 명 이상의 사람이 있는 것과 같은 사람들의 집합으로 정의된다고 가정합니다. 각 사람의 인덱스로 이러한 팀을 나타낼 수 있습니다. 예를 들어 팀이 [0, 1, 3]이라고 가정해 보겠습니다. 이것은 사람[0], 사람[1] 및 사람[3] 기술을 가진 사람을 나타냅니다.
가능한 가장 작은 규모의 팀을 찾아야 합니다.
어떤 순서로든 답을 반환할 수 있습니다. 답은 반드시 존재합니다.
따라서 입력이 req_skills =["java","flutter","android"], people =[["java"],["android"],["flutter","android"]]와 같은 경우 출력은 [0,2]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dp :=하나의 맵, 키 0에 해당하는 빈 목록 추가
-
key :=값은 req_skills에서 가져오고 i는 숫자인 (value,i)와 같은 맵
-
숫자의 경우 people 배열에서 사람 쌍(i, p)을 가져오고 번호를 할당합니다. -
-
current_skill :=0
-
p의 기술
-
current_skill :=current_skill OR 2^key[스킬]
-
-
for (skill_set,members) 쌍은 dp 키-값 쌍에 있습니다 -
-
total_skill :=Skill_set 또는 current_skill
-
total_skill이 Skill_set과 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
total_skill이 하지 않거나 크기가 dp[total_skill]> 구성원 크기 + 1인 경우
-
dp[total_skill] :=회원 + [i]
-
-
-
-
반환 dp[(1 <
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class Solution(object):
def smallestSufficientTeam(self, req_skills, people):
dp = {0:[]}
key = {v:i for i,v in enumerate(req_skills)}
for i,p in enumerate(people):
current_skill = 0
for skill in p:
current_skill |= 1<< key[skill]
for skill_set, members in dp.items():
total_skill = skill_set|current_skill
if total_skill == skill_set:
continue
if total_skill not in dp or len(dp[total_skill])>
len(members)+1:
dp[total_skill] = members + [i]
return dp[(1<<len(req_skills)) - 1]
ob = Solution()
print(ob.smallestSufficientTeam(["java","flutter","android"],
[["java"],["android"],["flutter","android"]])) 입력
["java","flutter","android"] [["java"],["android"],["flutter","android"]]
출력
[0,2]