[node.js] 가르침 ( 백준 1062번 )

// 백준 11723번 node.js는 메모리 제한으로 풀 수 없는 문제.
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];

const combinations = function* (elements, selectNumber) {
    for (let i = 0; i < elements.length; i++) {
        if (selectNumber === 1) {
            yield [elements[i]];
        } else {
            const fixed = elements[i];
            const rest = elements.slice(i + 1);

            for (const a of combinations(rest, selectNumber - 1)) {
                yield [fixed, ...a];
            }
        }
    }
};

rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    let [N, K] = input.splice(0, 1)[0].split(" ").map(Number);
    K -= 5;

    const words = input.map((el) => el.split("").splice(4, el.length - 8));
    const defaultStr = ["a", "n", "t", "i", "c"];
    if (K < 0) {
        console.log(0);
        return;
    } else if (K === 0) {
        const isAble = [...defaultStr];
        let count = 0;
        word: for (let i = 0; i < words.length; i++) {
            for (let j = 0; j < words[i].length; j++) {
                if (!isAble.includes(words[i][j])) {
                    continue word;
                }
            }
            count++;
        }

        console.log(count);
        return;
    } else if (K === 26) {
        console.log(N);
        return;
    } else {
        const restAlpha = [
            "b",
            "d",
            "e",
            "f",
            "g",
            "h",
            "j",
            "k",
            "l",
            "m",
            "o",
            "p",
            "q",
            "r",
            "s",
            "u",
            "v",
            "w",
            "x",
            "y",
            "z",
        ];

        let maxValue = 0;
        for (const a of combinations(restAlpha, K)) {
            const isAble = [...defaultStr, ...a];
            let count = 0;
            word: for (let i = 0; i < words.length; i++) {
                for (let j = 0; j < words[i].length; j++) {
                    if (!isAble.includes(words[i][j])) {
                        continue word;
                    }
                }
                count++;
            }

            if (maxValue < count) {
                maxValue = count;
            }
        }
        console.log(maxValue);
    }
});

그냥 때려 박는 게 마음이 편할 거 같다.
물론 그냥 때려 박았다고 해서, 아무런 생각없이 코드를 짠 것은 아닌데, 적어도 이 정도의 생각은 했다.
최대 50개의 단어
최대 15글자, 그런데 앞 뒤로 4글자씩 정해지니 7글자를 검사해야 한다고 볼 수 있겠다.
8개 글자는 총 5 종류의 알파벳이므로, 이미 5개는 정해졌다.
그러면 21개 중에서 K - 5개를 뽑아서 조합을 만든 다음에, 7번씩 비교를 50번 해주면 되겠구나.
그러면 21에서 가장 큰 조합이 나오는 건 10개, 11개를 뽑은 경우니 최대 복잡도를 계산하면,
35만 ( 21 중에서 10개를 뽑는 경우의 수 )에 7과 50를 곱하면 된다.
1억 2천만 정도가 나오니깐, 2천만 정도가 일단 오바된 거로 나오는데 아슬아슬하게 통과할 수도 있겠구나 싶었다.
( 1초 당 연산이 1억 번 된다고 가정했다. )

해본 결과, 통과했다.