2021.04.20
Solution1
Hashing & Slicing & BruteForce
- query를 슬라이싱합니다.
?가 접미사인 경우,?전까지 슬라이싱 합니다.?가 접두사인 경우, 뒤집어서?전까지 슬라이싱 합니다.- 전부
?인 경우, IsAll 변수에 표시합니다.
- words와 query를 비교합니다.
- 길이를 비교합니다. (다르면 더이상 확인할 필요 없습니다. => 거짓)
- query가 전부
?인 경우, 더이상 확인할 필요 없습니다. => 참 - words의 접두사 / 접미사와 슬라이싱한 query를 query의 길이만큼 전부 비교합니다.
- 이미 확인된 녀석은 Dictionary로 값을 기억하고 있다가 해당 쿼리가 다시 나타나면 그 값을 그대로 사용합니다.
결과 : 효율성 테스트케이스 1개 통과 못함 (2번 케이스)
import copy
def checkStr(word, query):
word = word[:len(query)]
if query == word:
return True
else:
return False
def solution(words, queries):
answer = []
Checked = {}
for q in queries:
back_q = copy.deepcopy(q)
if q in Checked:
answer.append(Checked[q])
continue
cnt = 0
IsReverse = False
IsAll = False
len_q = len(q)
idx = q.find('?')
if idx == 0:
IsReverse = True
q = q[::-1]
idx = q.find('?')
if idx == 0:
IsReverse = False
IsAll = True
q = q[:idx]
for w in words:
# 길이가 다른경우 일치할 수 없음
if len_q != len(w):
continue
# 길이가 같고 시작과 끝이 ? 인 경우 무조건 일치한다.
elif IsAll:
cnt += 1
continue
if IsReverse:
w = w[::-1]
if checkStr(w, q):
cnt += 1
answer.append(cnt)
Checked[back_q] = cnt
return answerSolution2
Trie & DFS
- Trie 자료구조에 모든 words와 뒤집은 words를 담습니다.
- Solution1 처럼 query를 slicing 합니다.
?가 접미사인 경우 words에서 starts_with 메서드로 해당되는 prefix를 가진 단어가 있는지 탐색합니다.?가 접두사인 경우 2-1 에서 뒤집은 words에서 탐색합니다.?로만 이루어진 경우 words에서 길이가 일치하는 단어 갯수를 완전탐색합니다.
결과
효율성 테스트 2,4번을 통과하지 못해서 starts_with 메서드에 매개변수를 추가해서
query의 길이와 동일할 때만 words에 추가하도록 변경했습니다.
그랬는데 4번을 통과하지 못했습니다.
class Node(object):
def __init__(self, key, data=None):
self.key = key # 값으로 입력될 문자
self.data = data # 문자열의 종료를 알리는 Flag (전체 문자열을 저장해서 구분)
self.children = {} # 자식노드를 저장
class Trie:
def __init__(self):
self.head = Node(None)
def insert(self, string):
current_node = self.head
for char in string:
if char not in current_node.children:
current_node.children[char] = Node(char)
current_node = current_node.children[char]
current_node.data = string
def search(self, string):
current_node = self.head
for char in string:
if char in current_node.children:
current_node = current_node.children[char]
else:
return False
if current_node.data:
return True
else:
return False
def starts_with(self, prefix, l):
current_node = self.head
words = []
for p in prefix:
if p in current_node.children:
current_node = current_node.children[p]
else:
return words
# DFS
current_node = [current_node]
next_node = []
while True:
for node in current_node:
if node.data and len(node.data) == l:
words.append(node.data)
next_node.extend(list(node.children.values()))
if len(next_node) != 0:
current_node = next_node
next_node = []
else:
break
return words
def solution(words, queries):
answer = []
Checked = {}
myTrie = Trie()
myReverseTrie = Trie()
for w in words:
myTrie.insert(w)
myReverseTrie.insert(w[::-1])
for q in queries:
if q in Checked:
answer.append(Checked[q])
continue
prefix_words = []
if q[0] == '?' and q[-1] == '?':
for w in words:
if len(w) == len(q):
prefix_words.append(w)
elif q[0] == '?':
qRev = q[::-1]
prefix_words = myReverseTrie.starts_with(qRev[:qRev.find('?')], len(q))
else:
prefix_words = myTrie.starts_with(q[:q.find('?')], len(q))
answer.append(len(prefix_words))
Checked[q] = len(prefix_words)
return answerSolution3
Trie & DFS
- 두번째 풀이에서 단어 길이가 긴 경우에 문자열의 종료에서만 길이비교해서 words를 거르는 경우가 생기면 결국에는 효율이 떨어지게 됩니다.
- 아예 그런 경우를 없애기 위해 words의 길이에 따라 따로 Trie를 만들어두고 query의 길이에 맞는 Trie를 탐색하도록 변경해서 효율성 테스트를 통과했습니다.
class Node(object):
def __init__(self, key, data=None):
self.key = key # 값으로 입력될 문자
self.data = data # 문자열의 종료를 알리는 Flag (전체 문자열을 저장해서 구분)
self.children = {} # 자식노드를 저장
class Trie:
def __init__(self):
self.head = Node(None)
def insert(self, string):
current_node = self.head
for char in string:
if char not in current_node.children:
current_node.children[char] = Node(char)
current_node = current_node.children[char]
current_node.data = string
def search(self, string):
current_node = self.head
for char in string:
if char in current_node.children:
current_node = current_node.children[char]
else:
return False
if current_node.data:
return True
else:
return False
def starts_with(self, prefix):
current_node = self.head
words = []
for p in prefix:
if p in current_node.children:
current_node = current_node.children[p]
else:
return words
# DFS
current_node = [current_node]
next_node = []
while True:
for node in current_node:
if node.data:
words.append(node.data)
next_node.extend(list(node.children.values()))
if len(next_node) != 0:
current_node = next_node
next_node = []
else:
break
return words
def solution(words, queries):
answer = []
Checked = {}
myTrie = [[Trie(), Trie()] for _ in range(10050)]
myReverseTrie = Trie()
for w in words:
myTrie[len(w)][0].insert(w)
myTrie[len(w)][1].insert(w[::-1])
for q in queries:
if q in Checked:
answer.append(Checked[q])
continue
prefix_words = []
if q[0] == '?' and q[-1] == '?':
for w in words:
if len(w) == len(q):
prefix_words.append(w)
else:
if q[0] == '?':
qRev = q[::-1]
prefix_words = myTrie[len(q)][1].starts_with(qRev[:qRev.find('?')])
else:
prefix_words = myTrie[len(q)][0].starts_with(q[:q.find('?')])
answer.append(len(prefix_words))
Checked[q] = len(prefix_words)
return answerSolution4
Binary Search
- 각 길이별로 단어를 정렬해서 딕셔너리에 담습니다.
- {5: ['frame', 'frodo', 'front', 'frost', 'kakao'], 6: ['frozen']}
- 접두사도 판단하기 위해 뒤집어서 하나 더 담습니다.
- {5: ['emarf', 'oakak', 'odorf', 'tnorf', 'tsorf'], 6: ['nezorf']}
- query로 탐색하는데, 접두사인지 접미사인지에 따라 ?를 a와 z로 바꿔준후 그 사이에 있는 단어들을 이진탐색합니다.
- bisect_left, bisect_right를 활용해서 탐색합니다.
- 예를 들어,
fro??로 탐색을 한다면,??를aa/zz로 바꾼 문자열 두개 사이의 문자열인 경우를 탐색하는 것입니다.['frame', 'frodo', 'front', 'frost', 'kakao'] 가 됩니다. - froaa ~ frozz 의 문자열이 탐색되는 것이고, 결과는
from collections import defaultdict
from bisect import bisect_left, bisect_right
def solution(words, queries):
answer = []
my_words = defaultdict(list)
my_reverse_words = defaultdict(list)
# 길이별로 딕셔너리에 담습니다
for word in words:
my_words[len(word)].append(word)
my_reverse_words[len(word)].append(word[::-1])
# 딕셔너리를 정렬합니다. (그래야 이진탐색이 가능하기 때문입니다.)
# O(NlogN)
for my_word in my_words.values():
my_word.sort()
for my_reverse_word in my_reverse_words.values():
my_reverse_word.sort()
# 이미 확인한 쿼리
Checked = defaultdict()
# 이진탐색을 합니다
# O(N * logM)
for query in queries:
# 중복 쿼리 Memoization
if query in Checked:
answer.append(Checked[query])
continue
# Binary Search
if query[0] == '?': # 와일드카드 접두사인 경우
target = my_reverse_words[len(query)]
start, end = query[::-1].replace('?','a'), query[::-1].replace('?','z')
else: # 와일드카드 접미사인 경우
target = my_words[len(query)]
start, end = query.replace('?','a'), query.replace('?','z')
Checked[query] = bisect_right(target, end) - bisect_left(target, start)
answer.append(Checked[query])
return answer
Comment