문제 📃
프로도는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았다.
여기서 키워드는 와일드 카드 문자 중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻한다.
'?'는 글자 하나를 의미하며 어떤 문자에도 매칭된다고 가정한다.
가사에 사용된 모든 단어들이 담긴 words배열과 찾고자 하는 키워드가 담긴 queries배열이 주어질 때 각 키워드 별로 매칭되는 단어가 몇 개인지 순서대로 배열에 담아 반환하는 문제이다.
풀이 ✏️
이 문제는 ... 외벽 점검문제 풀이 보다가~ 트라이 자료구조를 사용해야한다는 스포를 당해버려서 겁먹은 다음 트라이 자료구조에 대해 공부 먼저하고, 풀어본 문제이다.
트라이 자료구조
먼저 words 배열에 담긴 단어들을 트라이에 담아준다.
그리고 queries 배열에 담긴 키워드들을 하나씩 검색해주면 된다.
키워드에서 ?는 접두사 아니면 접미사 중 하나로만 등장하며, 키워드마다 하나 이상 존재한다.
따라서 fro??로 주어진 키워드라면 fro에 해당하는 문자열을 검색하고, 해당 문자열을 접두사로 갖는 단어가 몇 개인지 리턴 해준다.
?가 접두사로 주어진 ??odo와 같은 경우를 대비하여 문자열을 뒤집어서 삽입한 트라이도 생성해줘서 ?가 접두사라면 뒤집어진 문자열을 넣은 트라이를 사용하고 접미사라면 원본 트라이를 사용해서 검색해주면 된다.
단어의 수는 어떻게 구했냐면
그냥 문자열 하나를 추가할 때 마다, 추가하는 노드에 count변수를 하나씩 증가시켜 주면 된다.
만약 frodo라는 문자열을 추가한다면, f에서 r을 추가할 때 count증가, r에서 o를 추가할 때 count증가, 이런식으로 진행해준다. 그렇게 되면 f에서 r로 이동했을 때 r의 count가 fr이라는 문자열을 접두사로 가지는 단어의 수가 된다.
처음에 이렇게 구현을 했었는데, 이건 단어의 길이를 고려하지 않은 방법이었다.
?는 글자 하나를 의미하므로 fro??와 fro???는 다른 키워드인데, 이를 같은 키워드로 보는 것과 마찬가지였다.
그래서 이걸 어떻게 해결해야하나 했는데 의외로 간단한 방법으로 해결 가능했다.
바로 문자열의 길이마다 다른 트라이를 생성해주는 것이다.
Map<Integer,Trie> 형태의 맵을 사용하여 문자열의 길이가 5인 문자열만 존재하는 트라이는 키 값을 5로 저장해주고, 키워드를 검색할 때 키워드의 글자수에 해당하는 트라이를 사용해서 검색을 진행해줬다.
다음은 키 값이 5인 트라이고, 노드 옆 숫자는 count이다.
이런식으로 저장이 되고, fro??라는 키워드를 검색하기 위해서는 위의 트라이에서 fro까지 검색을 하고 ?를 만나는 순간 현재 노드에 저장된 count를 리턴해주면 된다.
코드 💻
import java.util.*;
class Trie {
Trie[] child = new Trie[26];
// 자식 노드의 수
int cnt = 0;
void insert(String str, int idx) {
// 문자열을 끝까지 다 확인했다면 리턴
if(idx == str.length())
return;
// 알파벳으로 삽입해야할 인덱스 구하기
int curIdx = str.charAt(idx) - 'a';
// 해당 child가 null 이면 새로 할당
if(child[curIdx] == null)
this.child[curIdx] = new Trie();
// 자식 수 늘려주고 남은 문자열 추가
this.cnt++;
this.child[curIdx].insert(str,idx+1);
}
int getCount(String query,int idx) {
// 현재 확인하고 있는 문자가 ?라면 현재 노드의 자손 수 리턴
char curChar = query.charAt(idx);
if(curChar == '?')
return this.cnt;
// 다음 문자 확인
int curIdx = query.charAt(idx) - 'a';
if(this.child[curIdx] != null)
return this.child[curIdx].getCount(query,idx+1);
// 다음 문자가 물음표도 아닌데 없는거면 없는 문자열이므로 0 리턴
return 0;
}
}
public class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = {};
// 트라이 맵 두 개 생성
// 키 : 문자열의 길이 / 값 : 트라이
Map<Integer,Trie> trieMap = new HashMap<>();
Map<Integer,Trie> rTrieMap = new HashMap<>();
// 길이 별로 다른 트라이에 문자열 삽입
for(String word : words) {
Trie trie = new Trie();
int len = word.length();
if(trieMap.containsKey(len))
trie = trieMap.get(len);
trie.insert(word, 0);
trieMap.put(len,trie);
// 물음표가 첫글자에 오는 쿼리 대비해서 문자열 뒤집은 트라이도 생성
String rword = new StringBuilder(word).reverse().toString();
Trie rTrie = new Trie();
if(rTrieMap.containsKey(len))
rTrie = rTrieMap.get(len);
rTrie.insert(rword, 0);
rTrieMap.put(len,rTrie);
}
answer = new int[queries.length];
int idx = 0;
for(String query : queries) {
int len = query.length();
int res = 0;
// ?로 시작하는 쿼리는 뒤집어진 트라이에서 검색
if(query.charAt(0) == '?') {
String rQuery = new StringBuilder(query).reverse().toString();
// 쿼리의 길이에 해당하는 트라이 꺼내서 검색
if(rTrieMap.containsKey(len))
res = rTrieMap.get(len).getCount(rQuery, 0);
answer[idx++] = res;
}
else {
if(trieMap.containsKey(len))
res = trieMap.get(len).getCount(query, 0);
answer[idx++] = res;
}
}
return answer;
}
}
