문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
풀이
Trie 알고리즘을 이용해서 효율성을 챙겼다.
접두사 또는 접미사만 나오기 때문에 가능했다.
검색을 하기 위해 세가지 조건이 필요하다.
- 두가지 모두 검색을 가능하게 하기 위해서 앞에서 부터 저장한 Trie 트리와 뒤에서 부터 저장한 Trie 트리를 두었다.
- word 와 query의 길이가 다를때 검색 되지 않기 위해 1 ~ 100000까지 길이 별로 Trie 트리를 만들었다.
- '?'가 나오면 모든 문자에 대해 검색을 하는 것이므로 현재까지의 단어의 갯수를 저장한다.
Trie트리를 구성할 노드클래스는 다음과 같다.
static class TrieNode{
int count;
HashMap<Character, TrieNode> childNode;
TrieNode(){
this.count = 0;
this.childNode = new HashMap<>();
}
}현재까지의 단어갯수를 저장할 int 변수와 다음 알파벳을 알려줄 HashMap<Character, TrieNode>를 가지고 있다.
Trie 트리를 구성하는 코드다.
public void insertBack(String query){
TrieNode node = back;
for(int i = query.length() - 1; i >= 0 ; i--){
node.count++;
if(!node.childNode.containsKey(query.charAt(i))){
node.childNode.put(query.charAt(i), new TrieNode());
}
node = node.childNode.get(query.charAt(i));
}
}
public void insertFront(String query){
TrieNode node = front;
for(int i = 0 ; i < query.length() ; i++){
node.count++;
if(!node.childNode.containsKey(query.charAt(i))){
node.childNode.put(query.charAt(i), new TrieNode());
}
node = node.childNode.get(query.charAt(i));
}
}앞에서 부터 저장하는 코드와 뒤에서 부터 저장하는 코드 두가지로 나누었다.
순서는 다음과 같다.
- 우선 현재의 알파벳의 count++을 해주어 단어수를 +1 해준다.
- 다음 알파벳의 TrieNode가 있다면 node 변수를 바꿔주고 없다면 생성후 바꿔준다.
query와 word 를 비교하여 갯수를 return 하는 메소드는 다음과 같다.
public int getCountBack(String query){
TrieNode node = back;
for(int i = query.length() -1; i >= 0 ; i--){
if(query.charAt(i) == '?'){
return node.count;
}
if(!node.childNode.containsKey(query.charAt(i))){
return 0;
}
node = node.childNode.get(query.charAt(i));
}
return node.count;
}위는 query가 접미사일 경우다.
코드 설명은 다음과 같다.
- 우선 뒤부터 저장한 TrieNode를 가져온다.
- query가 ? 라면 그앞의 문자들은 모두 ? 이므로 그때의 count를 return 한다.
- 다음 알파벳이 없다면 겹치는 단어가 없으므로 0을 return 한다.
- 다음 알파벳이 있다면 node를 다음 알파벳으로 바꿔준다.
- 단어의 끝까지 갔는데 return이 안됐다는건 query와 일치한 word가 있다는 것이므로 그때의 count를 return 한다.
위의 메소드들을 이용하여 Trie 트리를 구성하면 된다.
<전체코드>
import java.util.*;
class Solution {
public int[] solution(String[] words, String[] queries) {
int[] answer = new int[queries.length];
Trie[] trie = new Trie[100001];
for(int i = 0 ; i < words.length ; i++){
if(trie[words[i].length()] == null){
trie[words[i].length()] = new Trie();
}
trie[words[i].length()].insert(words[i]);
}
for(int i = 0 ; i < queries.length ; i++){
if(trie[queries[i].length()] == null){
answer[i] = 0;
continue;
}
answer[i] = trie[queries[i].length()].getCount(queries[i]);
}
return answer;
}
static class Trie{
TrieNode front;
TrieNode back;
Trie(){
front = new TrieNode();
back = new TrieNode();
}
public void insert(String query){
insertFront(query);
insertBack(query);
}
public void insertBack(String query){
TrieNode node = back;
for(int i = query.length() - 1; i >= 0 ; i--){
node.count++;
if(!node.childNode.containsKey(query.charAt(i))){
node.childNode.put(query.charAt(i), new TrieNode());
}
node = node.childNode.get(query.charAt(i));
}
}
public void insertFront(String query){
TrieNode node = front;
for(int i = 0 ; i < query.length() ; i++){
node.count++;
if(!node.childNode.containsKey(query.charAt(i))){
node.childNode.put(query.charAt(i), new TrieNode());
}
node = node.childNode.get(query.charAt(i));
}
}
public int getCount(String query){
if(query.charAt(0) == '?'){
return getCountBack(query);
}
return getCountFront(query);
}
public int getCountBack(String query){
TrieNode node = back;
for(int i = query.length() -1; i >= 0 ; i--){
if(query.charAt(i) == '?'){
return node.count;
}
if(!node.childNode.containsKey(query.charAt(i))){
return 0;
}
node = node.childNode.get(query.charAt(i));
}
return node.count;
}
public int getCountFront(String query){
TrieNode node = front;
for(int i = 0; i < query.length() ; i++){
if(query.charAt(i) == '?'){
return node.count;
}
if(!node.childNode.containsKey(query.charAt(i))){
return 0;
}
node = node.childNode.get(query.charAt(i));
}
return node.count;
}
}
static class TrieNode{
int count;
HashMap<Character, TrieNode> childNode;
TrieNode(){
this.count = 0;
this.childNode = new HashMap<>();
}
}
}'자료구조 공부 > Trie' 카테고리의 다른 글
| [프로그래머스] 자동 완성 (0) | 2021.07.25 |
|---|---|
| 백준 5052 (전화번호 목록) -Trie (0) | 2021.05.02 |
| 백준 9202 (Boggle) (0) | 2021.03.16 |