프로젝트를 진행할 때 필요한 스킬 목록 req_skills과 사람 목록 people이 주어진다고 가정해 봅시다. 여기서 i번째 사람인 people[i]는 해당 사람이 보유한 스킬들의 리스트를 나타냅니다.
문제 정의
충분한 팀(sufficient team)이란, req_skills에 포함된 모든 필수 스킬을 팀원 중 적어도 한 명이 가지고 있는 사람들의 집합을 의미합니다. 이러한 팀은 각 사람의 인덱스로 표현할 수 있습니다. 예를 들어 팀이 [0, 1, 3]이라면, 이는 people[0], people[1], people[3] 세 명으로 구성된 팀을 뜻합니다.
우리의 목표는 가능한 한 가장 작은 크기의 충분한 팀을 찾는 것입니다. 답은 어떤 순서로든 반환할 수 있으며, 항상 답이 존재한다고 보장됩니다.
입력 및 출력 예시
예를 들어, 입력이 다음과 같다면:
req_skills = ["java", "flutter", "android"]people = [["java"], ["android"], ["flutter", "android"]]
출력은 [0, 2]가 됩니다. 즉, 0번 사람(java 보유)과 2번 사람(flutter, android 보유) 두 명만으로 모든 필수 스킬을 커버할 수 있습니다.
풀이 접근 방법
이 문제는 비트마스크(bitmask) 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 각 스킬을 비트 하나로 매핑하면, 스킬 조합을 하나의 정수로 표현할 수 있습니다. 단계별로 살펴보겠습니다.
- DP 테이블 초기화:
dp라는 맵(딕셔너리)을 만들고, 키 0(아무 스킬도 없는 상태)에 빈 리스트를 대응시킵니다. - 스킬 인덱싱:
key라는 맵을 만들어req_skills의 각 스킬을 고유한 번호(비트 위치)로 매핑합니다. - 각 사람 처리:
people배열을 순회하며 각 사람(i번째 사람 p)에 대해:current_skill을 0으로 초기화합니다.- p가 가진 각 스킬에 대해
current_skill에2^key[skill](비트 OR 연산)를 누적합니다. 이렇게 하면 그 사람의 스킬 집합이 하나의 비트마스크로 표현됩니다.
- 기존 상태와 조합: dp에 저장된 모든 (skill_set, members) 쌍에 대해:
total_skill = skill_set | current_skill을 계산합니다.total_skill이skill_set과 같다면, 새로운 스킬이 추가되지 않았으므로 건너뜁니다.total_skill이 아직 dp에 없거나, 기존에 저장된 팀 크기가members + [i](현재 사람을 추가한 팀)보다 크다면,dp[total_skill] = members + [i]로 갱신합니다.
- 정답 반환: 모든 스킬을 커버하는 상태인
dp[(1 << len(req_skills)) - 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 list(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]
동작 원리 정리
핵심 아이디어는 다음과 같습니다. n개의 스킬을 비트로 표현하면 전체 스킬 집합의 상태 공간은 최대 2^n개입니다. dp의 각 키는 '지금까지 확보한 스킬 집합'을 의미하고, 그 값은 '그 상태를 달성하기 위한 최소 팀 구성'을 저장합니다. 새로운 사람을 추가했을 때 도달 가능한 새로운 스킬 상태마다, 더 작은 팀으로 도달할 수 있다면 갱신하는 방식으로 최적해를 구합니다.
이 알고리즘의 시간 복잡도는 O(2^N × M)입니다. 여기서 N은 필수 스킬의 개수, M은 사람 수입니다. 스킬 개수가 최대 60개까지 허용되므로 비트마스크를 활용하면 메모리와 속도 면에서 매우 효율적인 풀이가 됩니다.