문제
문제 설명
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 단어 제한사항
words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
검색 키워드는 중복될 수도 있습니다.
각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
풀이1
효율성을 고려하지 못한 채 선형으로 이중 for문을 사용해서 풀이하였다.
function solution(words, queries) {
const answer=[];
const trie = new Trie()
for(let i=0;i<queries.length;i++){
const query=queries[i];
let num=0;
for(let j=0;j<words.length;j++){
const word= words[j];
if(word.length!==query.length)continue;
for(let n=0;n<word.length;n++){
if(query[n]=="?"){
if(n==word.length-1)num++;
continue;
}
if(word[n]!==query[n])break;
if(n==word.length-1)num++;
}
}
answer.push(num);
}
return answer;
}괜찮은 풀이 였는지, 효율성 1,2,3을 제외한 모든 케이스는 통과를 하였다.
풀이2
문자열을 검색하는 부분이므로, Trie구조를 이용하였다.
위 링크에 있는 Trie 구현 방법을 동일하게 이용하였으며, Trie에 삽입할 때, 검색할 때 약간의 추가요소가 있었다.
Trie는 각 단어의 길이가 얼마나 되는 지를 구분하여, Trie를 구성한다.
그리고 물음표가 나오게 되면 그 이하에 단어가 몇개가 있는지를 바로 return 할 수 있도록, TrieNode의 기본 scheme에 count를 넣어준다. 그리고, insert 될 때마다, 각 단에서 count++할 수 있도록 한다.
물음표 부터 시작할 시에는, 역으로 reverse된 계산을 하도록 한다. 이를 위해, 처음부터 rearTrie도 동시에 생성해 준다.
function TrieNode() {
this.children = {};
this.isEndOfWord = false;
this.count = 0;
//count 추가
}
function Trie() {
this.root = new TrieNode();
}
Trie.prototype.insert = function (word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
let node = current.children[ch];
if (node === undefined) {
node = new TrieNode();
current.children[ch] = node;
}
current.count++;
//추가 되는 level마다 count++
current = node;
}
current.endOfWord = true;
};
Trie.prototype.search = function (word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (ch == '?') return current.count;
//?가 나온다면 그 이하에 단어의 개수를 출력해 준다.
let node = current.children[ch];
if (node == undefined) {
return 0;
}
current = node;
}
return current.count;
};
function solution(words, queries) {
const frontTrie = Array.from({ length: 10001 }, () => new Trie());
const rearTrie = Array.from({ length: 10001 }, () => new Trie());
// 단어의 길이별로 Trie를 구성하며, 역계산을 위한 rearTrie 같이 생성
const answer = [];
for (let word of words) {
const n = word.length;
frontTrie[n].insert(word);
rearTrie[n].insert(word.split('').reverse().join(''));
//rearTrie도 같이 insert
}
for (let query of queries) {
const n = query.length;
if (query[0] !== '?') {
//물음표로 시작하지 않는것
answer.push(frontTrie[n].search(query));
} else {
//물음표로 시작하는것
answer.push(rearTrie[n].search(query.split('').reverse().join('')));
}
}
return answer;
}
