1062번 - 가르침

1️⃣ 비트마스킹

 

✏️ 풀이 과정

정보의 형태를 변환하면 생각보다 가짓수가 적게 나오는 문제입니다. 어떤 알파벳이 등장하는 지가 중요하기 때문에 문장이 주어지면 이를 비트마스킹을 이용해서 어떤 알파벳들이 쓰였는지에 대한 정보로 바꿀 수 있습니다. 알파벳이 총 26개이기 때문에 26bit 안으로 간단하게 변환이 가능합니다.(가령 a가 있으면 1<<0에 표시 b가 있으면 1<<1에 표시)

 

이 정보들을 구했다면 나머지는 K개의 알파벳을 사용하는 가능한 모든 조합과 비교해서 가장 해당 조합이 포괄하는 단어가 많은 경우를 구하면 됩니다. 이는 비트 연산자 &를 이용해서 간단하게 구현할 수 있습니다.

 

처음에 저장해놓은 모든 정보들에 대해 조합 결과를 비트마스킹으로 변환한 결과와 AND연산을 했을 때 해당 정보가 그대로 유지되면(즉 조합 결과의 해당 부분이 모두 1일 때) 카운팅을 해주면 됩니다.

 

각 조합마다 카운팅을 해주면서 최댓값을 갱신하면 문제가 해결됩니다.

 

여기서 a, n, t, i, c의 5개의 알파벳은 고정이기 때문에 이를 미리 고려하고 시작하면 계산 횟수를 크게 줄일 수 있습니다.

 

⏱ 시간 복잡도

조합을 사용해서 전체 경우의 수를 따져 N개의 수와 비교하는 부분이 핵심이기 때문에 시간 복잡도는 O(21^(K-5) * N)이 됩니다.

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const [N, K] = input[0].split(" ").map(Number);
const words = [];
for (let i = 1; i <= N; i++) {
    let bit = 0;
    const str = input[i];
    for (let j = 0; j < str.length; j++) {
        for (let k = 0; k < 26; k++) {
            if (str.charCodeAt(j) === "a".charCodeAt(0) + k) {
                bit |= 1 << k;
            }
        }
    }
    words.push(bit);
}
let ans = 0;
let origin = 0;
const init = [0, 2, 8, 13, 19];
init.forEach((item) => {
    origin |= 1 << item;
});
const R = K - 5;

const rest = [
    1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25,
];
let res = [];

const comb = (n, start) => {
    if (n === R) {
        let tmp = origin;
        res.forEach((item) => {
            tmp |= 1 << item;
        });
        let cnt = 0;
        words.forEach((word) => {
            if ((word & tmp) === word) {
                cnt++;
            }
        });
        if (cnt > ans) {
            ans = cnt;
        }
        return;
    }

    for (let i = start; i < 21; i++) {
        res[n] = rest[i];
        comb(n + 1, i + 1);
    }
};

comb(0, 0);
console.log(ans);