백준[node.js] > 1141번 접두사

 

 

문제링크

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

 

문제풀이

문자들을 비교하면서 문자가 긴 단어일 수록 다른 단어의 접두어가 될 확율이 떨어진다. 이를 고려하여 두 단어중 하나의 단어가 다른 단어의 접두어가 될 때 두 문자중 이왕이면 긴 문자를 집합에 포함함으로 써 최대한 많은 단어를 집합에 포함시킬 수 있다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let dic = [];
for (let i = 1; i <= input.length - 1; ++i) {
    let word = input[i];
    let isOverlap = false;

    for (let j = 0; j <= dic.length - 1; j++) {
        let ref = dic[j];
        if (ref.startsWith(word) === true || word.startsWith(ref) === true) {
            dic[j] = ref.length <= word.length ? word : ref;
            isOverlap = true;
            break;
        }
    }

    if (!isOverlap) {
        dic.push(word);
    }
}
console.log(dic.length);