문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
입출력 예시
words
["frodo", "front", "frost", "frozen", "frame", "kakao"]queries
["fro??", "????o", "fr???", "fro???", "pro?"]result
[3, 2, 4, 1, 0]입출력 예시 설명
- "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
- "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
- "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
- "fro???"는 "frozen"에 매치되므로 1입니다.
- "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.
풀이
[문제 간단 정리!]
문제 설명과 예시가 길지만, 짧게 정리하면 이렇다!
입력으로는 가사에 등장하는 단어로 이뤄진 배열 words와 검색 키워드로 이뤄진 배열 queries가 들어온다.
검색 키워드는 알파벳 소문자와 ‘?’로만 구성되어 있고, '?'는 접두사 맨 앞이나 뒤에만 온다. ‘fro?t’나 ‘f?o?t’ 같은 키워드는 입력으로 들어오지 않는 다는 말이다!
그래서 이렇게 들어온 검색 키워드(queries)를 가지고, 매치되는 단어의 수를 배열로 반환하는 것이 문제이다.
[접근]
가장 단순한 방법은 Brute Fore(완전탐색) 을 사용하여 각 키워드마다, words 배열을 돌면서 포함되는 것이 있는지 확인하는 것이다.
words의 최대 길이가 100,000, queries의 최대 길이도 100,00이기 때문에 문제를 해결할 수야 있겠지만, 효율성면에서는 완전 0점이다!
효율성까지 고려해서 생각하면, Trie를 사용해서 풀어야 한다!
문제의 조건을 잘 보면, 검색 키워드의 맨 앞이나 뒤에 반드시 '?'가 하나씩 포함된다. 이게 어떤 의미인지 생각해보면, "문자열의 시작과 끝을 반드시 알 수 있다"는 것을 이해할 수 있을 것이다.
Trie를 사용하여 문제를 푸는 것 까지 생각했다면, 다음은 Result 조건을 살펴보자.
??를 제외한 queries가 단어와 동일하다.
??를 포함한 queries의 길이가 단어의 길이와 동일하다.
첫번째 조건은 Trie를 사용하면 쉽게 찾아낼 수 있디.
그러나 일반적인 Trie를 사용하면, 검색 키워드가 접미사로 들어오는 경우에는 검색할 수 없다. 그래서 모든 단어를 반대로 해서 만든 Trie도 같이 사용해야 한다.
접두사로 검색 키워드를 확인하는 경우(ex. abc?) => 일반 Trie
접미사로 검색 키워드를 확인하는 경우(ex. ???o) => 반대 Trie
두번째 조건은 어떻게 확인할 수 있을까?
Trie 자료구조에 현재 index(word의 몇번째 단어) 분기에서 단어가 몇개있는지 저장을 한다. insert 마다 count++를 해주면 해당 분기에서 몇개의 단어가 등록되어있는지 알 수 있다.
이를 구현하기 위해, 하나의 루트를 가진 Trie가 아닌 Trie들을 배열로 만들어서 관리해 준다. 배열로 만들어서 관리를 해준 이유는 "문자열의 길이" 때문이다. 문자열을 길이별로 Tri를 따로 저장하는 것이다.
예를 들어서 "abcde"가 있다면, Trie Trie[5] 에 저장을 해주었다. 여기서 5번 Index에 저장을 해준 것은, "문자열의 길이가 5입니다" 라는 것을 의미한다. 검색키워드에서도 문자열의 길이에 따라서 답이 달라지기 때문에 이런 식으로 관리해야 한다.
예를 들어, Tire[5]는 이런 식으로 구성된다.
정리하자면,
1 . 양방향 Trie 구조를 만든다.
2. queries를 탐색할 때 정방향 , 역방향 알맞게 getCount를 수행한다.
3. 처음으로 ?가 나오는 순간에 현재 노드에 등록된 단어수를 반환한다.
4. 만약 null값이 나온다면 사전에 등록되어 있지 않다는 뜻이니 0을 반환한다.
Code
class Trie {
constructor() {
this.children = {};
this.count = 0;
}
insert(word) {
let trie = this;
++this.count;
for (const letter of word) {
if (typeof trie.children[letter] === 'undefined') {
trie.children[letter] = new Trie();
}
trie = trie.children[letter];
++trie.count;
// 문자열이 삽입될 때마다 count
// queries에 있는 문자열들을 search했을 때 길이가 같은 단어가 몇개인지 바로 알 수 있음
}
}
// node에 등록되어 있는 단어의 수를 return
getCount(query) {
let trie = this;
for (const letter of query) {
if (letter === '?') {
return trie.count;
} else if (typeof trie.children[letter] === 'undefined') {
return 0;
}
trie = trie.children[letter];
}
}
}
function solution(words, queries) {
const tries = {}; // 일반 Trie
const reverseds = {}; // Reverse Trie
for (const word of words) {
const length = word.length;
//단어의 길이을 구하고, 그 길이에 해당하는 Trie 배열에 새로운 Trie를 추가해주면 됩니다.
// ex) length = 5, 길이가 5인 Trie들이 모인 Trie[5]에 해당 단어를 추가해주면 됩니다.
if (typeof tries[length] === 'undefined') {
tries[length] = new Trie();
reverseds[length] = new Trie();
}
// 인덱스가 tries[i]의 길이값인 곳에 단어 길이 i인 문자열만 삽입된 tries, reverseds를 만듦
// ?가 뒤에 있는 경우
tries[length].insert(word);
// ?가 앞에 있는 경우
reverseds[length].insert([...word].reverse().join(''));
}
return queries.map((query) => {
const length = query.length;
// 해당 length에 해당하는 Trie 배열을 탐색
// 만약 undefined값이 나온다면 사전에 등록되어 있지 않은 것 -> 0반환
if (typeof tries[length] === 'undefined') {
return 0;
}
// 처음으로 ?가 나오는 순간에 현재 노드의 등록된 단어수를 반환
if (query[0] === '?') {
return reverseds[length].getSum([...query].reverse().join(''));
}
return tries[length].getCount(query);
});
}Reference
