[LeetCode] 1125. Smallest Sufficient Team (Hard)

이 문제를 풀기 위해서는 비트마스크 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 배열을 복사해서 기준으로 삼는 것이다.

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이기 때문에 이 방식은 충분히 통과 가능하다.

참고자료

• LeetCode: https://leetcode.com/problems/smallest-sufficient-team/