이 문제를 풀기 위해서는 비트마스크 DP에 대해서 알아야 한다.
비트마스크는 여러 개의 참/거짓 상태를 하나의 정수로 압축하는 방법이다. 이 문제에서는 필요한 스킬의 개수가 최대 16개이므로, 각 스킬을 비트 하나에 대응시키면 어떤 팀이 가진 스킬 조합을 숫자 하나로 표현할 수 있다. 그리고 그 숫자를 DP의 상태로 쓰면, "이 스킬 조합을 만들 수 있는 가장 작은 팀"을 차근차근 갱신할 수 있다.
스킬을 비트마스크로 바꾸기
0. 필요한 개념 먼저 정리하기
먼저 비트마스크부터 보자. 예를 들어 필요한 스킬이 ["java", "nodejs", "reactjs"]라면 다음처럼 위치를 정할 수 있다.
java-> 0번 비트nodejs-> 1번 비트reactjs-> 2번 비트
그러면 ["nodejs", "reactjs"]를 가진 사람은 110이라는 마스크로 표현된다. 팀에 사람을 추가할 때는 기존 팀의 마스크와 새 사람의 마스크를 OR 연산하면 된다.
const nextMask = mask | personMask;이제 DP 상태를 정의할 수 있다.
dp[mask] = mask에 해당하는 스킬 조합을 만들 수 있는 가장 작은 팀
예를 들어 dp[0101] = [0, 3]이라면, 사람 0번과 3번을 고르면 0101에 해당하는 스킬들을 커버할 수 있고, 지금까지 발견한 방법 중 팀 크기가 가장 작다는 뜻이다.
1. 접근 : 문제를 단순화 하기
문제는 필요한 스킬 목록 req_skills와 각 사람이 가진 스킬 목록 people이 주어졌을 때, 모든 필요 스킬을 커버하는 가장 작은 사람 인덱스 집합을 찾는 것이다. 정답은 여러 개일 수 있고, 그중 아무 하나를 반환하면 된다.
사람 수는 최대 60명이다. 사람의 모든 부분집합을 검사하면 2^60이 되므로 불가능하다. 하지만 필요한 스킬 수는 최대 16개다. 따라서 사람 조합을 직접 상태로 두지 말고, 스킬 조합을 상태로 두면 가능한 상태 수는 최대 2^16 = 65536개로 줄어든다.
여기서 중요한 포인트는 다음과 같다.
- 사람은 최대 60명이지만, 스킬 조합은 최대 65536개뿐이다.
- 각 사람을 하나씩 보면서, 그 사람을 추가했을 때 더 작은 팀이 만들어지는지만 확인하면 된다.
- 최종 목표 상태는 모든 비트가 켜진
fullMask다.
2. 핵심 아이디어
각 사람을 순서대로 보면서 DP를 갱신한다.
현재 어떤 스킬 조합 mask를 만들 수 있다고 하자. 여기에 사람 i를 추가하면 새 조합은 mask | personMask가 된다. 만약 이 새 조합을 만들 팀이 아직 없거나, 기존 팀보다 dp[mask] + i가 더 작다면 갱신한다.
비트마스크 DP 전이
주의할 점은 한 사람을 처리하는 동안 그 사람을 같은 팀에 여러 번 넣지 않도록, 갱신 전의 DP 배열을 복사해서 기준으로 삼는 것이다.
const before = dp.slice();이렇게 하면 현재 사람 i를 추가하는 전이는 항상 "사람 i를 보기 전까지 만들어진 팀"에서만 출발한다.
3. 단계별로 구현하기
3-1. 스킬을 비트 위치로 바꾸기
먼저 필요한 스킬마다 비트 위치를 부여한다.
const skillToBit = new Map();
for (let i = 0; i < req_skills.length; i++) {
skillToBit.set(req_skills[i], i);
}그리고 각 사람의 스킬 목록도 하나의 마스크로 바꾼다.
let personMask = 0;
for (const skill of people[i]) {
personMask |= 1 << skillToBit.get(skill);
}3-2. DP 배열 초기화하기
dp[mask]에는 해당 스킬 조합을 만드는 사람 인덱스 배열을 저장한다. 아직 만들 수 없는 조합은 null로 둔다.
const fullMask = (1 << req_skills.length) - 1;
const dp = Array(1 << req_skills.length).fill(null);
dp[0] = [];아무 스킬도 필요하지 않은 상태 0은 빈 팀으로 만들 수 있으므로 dp[0] = []가 된다.
3-3. 사람을 하나씩 추가해보기
각 사람에 대해 기존의 모든 스킬 조합을 확인한다. 새 조합이 더 작은 팀으로 만들어진다면 갱신한다.
const before = dp.slice();
for (let mask = 0; mask <= fullMask; mask++) {
if (before[mask] === null) continue;
const nextMask = mask | personMask;
if (dp[nextMask] === null || dp[nextMask].length > before[mask].length + 1) {
dp[nextMask] = [...before[mask], i];
}
}이때 스킬을 하나도 새로 추가하지 못하는 사람이어도 로직은 안전하다. nextMask가 기존 mask와 같아지고, 팀 크기는 오히려 늘어나므로 갱신되지 않는다.
4. 최종 구현
/**
* @param {string[]} req_skills
* @param {string[][]} people
* @return {number[]}
*/
var smallestSufficientTeam = function(req_skills, people) {
const skillToBit = new Map();
for (let i = 0; i < req_skills.length; i++) {
skillToBit.set(req_skills[i], i);
}
const fullMask = (1 << req_skills.length) - 1;
const dp = Array(1 << req_skills.length).fill(null);
dp[0] = [];
for (let i = 0; i < people.length; i++) {
let personMask = 0;
for (const skill of people[i]) {
personMask |= 1 << skillToBit.get(skill);
}
const before = dp.slice();
for (let mask = 0; mask <= fullMask; mask++) {
if (before[mask] === null) continue;
const nextMask = mask | personMask;
if (dp[nextMask] === null || dp[nextMask].length > before[mask].length + 1) {
dp[nextMask] = [...before[mask], i];
}
}
}
return dp[fullMask];
};5. 시간복잡도
m을 필요한 스킬 개수, n을 사람 수라고 하자.
- 시간복잡도:
O(n * 2^m * m) - 공간복잡도:
O(2^m * m)
각 사람마다 가능한 모든 스킬 조합을 순회한다. 또한 팀 배열을 복사할 때 최대 m명 정도의 인덱스를 담을 수 있으므로 위와 같이 볼 수 있다. m <= 16이기 때문에 이 방식은 충분히 통과 가능하다.
참고자료
'Computer Sci. > Algorithms' 카테고리의 다른 글
| [LeetCode] 1820. Maximum Number of Accepted Invitations (Medium) (0) | 2026年07月08日 |
|---|---|
| [LeetCode] 3600. Maximize Spanning Tree Stability with Upgrades (Hard) (0) | 2026年03月20日 |
| [알고리즘 문제 해결 전략] Ch03-3. 알고리즘 설계 패러다임 (동적 계획법) (0) | 2022年05月25日 |
| [C.C.I] 02. 연결리스트 (0) | 2022年04月29日 |
| [C.C.I] 01. 배열과 문자열 (0) | 2022年04月28日 |