백준 1062 가르침 | JavaScript 비트마스킹

https://www.acmicpc.net/problem/1062

어떻게 풀어야할지 감이 안 와서 그냥 배운 단어에 대한 배열을 만들고, 배열을 순회하며 문자를 하나하나 비교했다 ..

이미 읽을 수 있는 "anta", "tica"에 포함되어있는 [a,n,t,i,c]를 제외한 21개의 글자에 대해서 부분조합을 만들고, 만들어진 부분조합과 [a,n,t,i,c]를 합쳤다.

const fs = require("fs");
const input = fs.readFileSync(0, "utf-8").trim().split("\n");

const [N, K] = input[0].split(" ").map(Number);
const words = input.slice(1).map((line) => line.split(""));

// 이미 알고 있는 단어
const learned = ["a", "n", "t", "i", "c"];

// 새로 배울 단어
const ALPHABET = Array.from({ length: 26 }, (_, i) => String.fromCharCode(i + 97));
const notlearnd = ALPHABET.filter((el) => !learned.includes(el));

// anta, tica를 제외하고 읽어야하는 단어
const readWords = [];

for (let i = 0; i < N; i++) {
  readWords.push(words[i].slice(4, -4));
  //console.log(readWords);
}

function solution(notlearnd, K) {
  let max = 0;
  function backtrack(start, comb) {
    if (comb.length === K) {
      // 조합 완성되면
      let cnt = 0;

      // 이미 배운 단어 + 새로 배운 단어
      const learnedComb = comb.concat(learned);

      // 배운 단어와 같으면?
      for (let i = 0; i < readWords.length; i++) {
        let canRead = true;

        for (let j = 0; j < readWords[i].length; j++) {
          if (!learnedComb.includes(readWords[i][j])) {
            canRead = false;
            break;
          }
        }
        // console.log("읽을수잇어?", readWords[i], canRead);
        if (canRead) {
          cnt++; // 읽을 수 있을 때만 카운트
          //console.log(cnt);
        }
      }

      if (cnt === N) {
        max = cnt;
        return;
      }
      max = Math.max(max, cnt);
    }
    for (let i = start; i < notlearnd.length; i++) {
      comb.push(notlearnd[i]);
      backtrack(i + 1, comb);
      comb.pop();
    }
  }

  backtrack(0, []);
  return max;
}

console.log(solution(notlearnd, K - 5));

시간 제한이 1초인데 왜 맞았는지는 잘 모르겠다 ..

배운 단어를 배열로 관리하면 읽을 수 있는 단어인지 확인하기 위해서는 26개의 알파벳에 대해서 모두 순회하며 비교해야하기 때문에 효율이 좋지 않다.

이를 배운 단어인가?에 대해 2진수 값으로 저장하면 한번의 연산만으로 읽을 수 있는 단어인지 확인할 수 있다.

예를 들어, 읽을 단어가 antarctica이고 새로 가르칠 단어가 3개라면 이 단어는 읽을 수 있다.

읽을 단어가 antahellotica이고 새로 가르칠 단어가 3개라면 이 단어는 읽을 수 없다.

배운 단어 & 읽을 단어 == 읽을 단어

배운 단어 | 읽을 단어 == 배운 단어

이를 비트연산으로 표현하면 이렇게 두가지 방법이 가능하다.

전체 코드

const fs = require("fs");
const input = fs.readFileSync(0, "utf-8").trim().split("\n");

const [N, K] = input[0].split(" ").map(Number);
const words = input.slice(1).map((line) => line.split(""));

// 이미 알고 있는 단어
const learned = ["a", "n", "t", "i", "c"];

let learnedMask = 0;
for (let i = 0; i < learned.length; i++) {
  learnedMask |= 1 << (learned[i].charCodeAt(0) - 97);
}
// console.log(notlearnd.toString(2));

let wordMask = new Array(N).fill(0);
for (let i = 0; i < N; i++) {
  const middle = words[i].slice(4, -4);
  for (const ch of middle) {
    wordMask[i] |= 1 << (ch.charCodeAt(0) - 97);
  }
  // console.log(wordMask[i].toString(2));
}

let max = 0;
function masking(start, cnt, mask) {
  if (cnt === K - 5) {
    // 조합 완성되면
    let readCnt = 0;
    for (const wMask of wordMask) {
      if ((wMask & mask) === wMask) readCnt++;
    }
    max = Math.max(max, readCnt);
    return;
  }
  for (let i = start; i < 26; i++) {
    if ((learnedMask & (1 << i)) !== 0) continue;
    masking(i + 1, cnt + 1, mask | (1 << i));
  }
}

if (K < 5) console.log(0);
else {
  masking(0, 0, learnedMask);
  console.log(max);
}

연산 속도 차이가 어마어마하다 .. 비트마스킹을 잘 활용해야겠다.