코딩 테스트/Level 4
2020 KAKAO BLIND RECRUITMENT 가사 검색
컴닥
2022. 12. 4. 22:06
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/60060
BF로 확인..
def solution(words, queries):
import re
answer = [0] * len(queries)
for index, query in enumerate(queries):
q = re.compile(f"^{query}$".replace("?", "."))
for word in words:
if q.search(word) is not None:
answer[index] += 1
return answer당연히..
정확성 테스트
테스트 1 〉 통과 (1.79ms, 10.3MB)
테스트 2 〉 통과 (1.12ms, 10.2MB)
테스트 3 〉 통과 (1.21ms, 10.1MB)
테스트 4 〉 통과 (1.34ms, 10.1MB)
테스트 5 〉 통과 (1.40ms, 10.2MB)
테스트 6 〉 통과 (1.39ms, 10.2MB)
테스트 7 〉 통과 (16.88ms, 10.3MB)
테스트 8 〉 통과 (20.25ms, 10.2MB)
테스트 9 〉 통과 (23.47ms, 10.4MB)
테스트 10 〉 통과 (14.94ms, 10.2MB)
테스트 11 〉 통과 (14.20ms, 10.3MB)
테스트 12 〉 통과 (17.09ms, 10.3MB)
테스트 13 〉 통과 (222.45ms, 10.5MB)
테스트 14 〉 통과 (191.67ms, 10.6MB)
테스트 15 〉 통과 (225.41ms, 10.4MB)
테스트 16 〉 통과 (212.51ms, 10.5MB)
테스트 17 〉 통과 (188.19ms, 10.6MB)
테스트 18 〉 통과 (233.41ms, 10.6MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 통과 (499.61ms, 15.1MB)
테스트 5 〉 통과 (1274.58ms, 19.8MB)Trie
중간에 '?'가 나와도 검색이 되도록 재귀로 만들어 보았다.
문제 조건에서도 재귀의 한계를 넘기는 숫자들이 보인다.
될리가 없다.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
current = self.root
for letter in word:
current.setdefault(letter, {})
current = current[letter]
current['*'] = word
def search(self, word, index=0, current=None, match=0):
if current is None:
current = self.root
if index == len(word):
return match + 1 if '*' in current else match
letter = word[index]
if letter in current:
match = self.search(word, index + 1, current[letter], match)
elif letter == '?':
for letter in current:
match = self.search(word, index + 1, current[letter], match)
return match
def solution(words, queries):
import sys
sys.setrecursionlimit(1_000_000)
trie = Trie()
for word in words:
trie.insert(word)
return [trie.search(query) for query in queries]Trie를 글자수 별로 만들어서 같은 글자수끼리 비교한다.
class Node:
def __init__(self):
self.count = 0
self.children = {}
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word):
current = self.root
current.count += 1
for letter in word:
if letter not in current.children:
current.children[letter] = Node()
current = current.children[letter]
current.count += 1
current.children['*'] = word
def search(self, word):
current = self.root
for letter in word:
if letter not in current.children:
return 0
current = current.children[letter]
return current.count
def solution(words, queries):
tries = {}
r_tries = {}
for word in words:
tries.setdefault(len(word), Trie())
r_tries.setdefault(len(word), Trie())
tries[len(word)].insert(word)
r_tries[len(word)].insert(word[::-1])
return [search_helper(tries, r_tries, query) for query in queries]
def search_helper(tries, r_tries, query):
modified_query = query.replace('?', '')
if len(query) not in tries:
return 0
if query[0] != '?':
return tries[len(query)].search(modified_query)
if query[-1] == '?':
return tries[len(query)].root.count
return r_tries[len(query)].search(modified_query[::-1])정확성 테스트
테스트 1 〉 통과 (1.15ms, 10.5MB)
테스트 2 〉 통과 (0.25ms, 10.2MB)
테스트 3 〉 통과 (0.43ms, 10.3MB)
테스트 4 〉 통과 (0.40ms, 10.2MB)
테스트 5 〉 통과 (0.27ms, 10.3MB)
테스트 6 〉 통과 (0.46ms, 10.3MB)
테스트 7 〉 통과 (12.00ms, 12.6MB)
테스트 8 〉 통과 (5.23ms, 10.9MB)
테스트 9 〉 통과 (6.59ms, 12.6MB)
테스트 10 〉 통과 (8.23ms, 12.8MB)
테스트 11 〉 통과 (4.71ms, 10.9MB)
테스트 12 〉 통과 (6.87ms, 12.6MB)
테스트 13 〉 통과 (45.06ms, 22MB)
테스트 14 〉 통과 (26.86ms, 15.3MB)
테스트 15 〉 통과 (59.42ms, 21.4MB)
테스트 16 〉 통과 (43.93ms, 22.4MB)
테스트 17 〉 통과 (14.69ms, 14.9MB)
테스트 18 〉 통과 (36.08ms, 21.2MB)
효율성 테스트
테스트 1 〉 통과 (1253.92ms, 201MB)
테스트 2 〉 통과 (2919.92ms, 378MB)
테스트 3 〉 통과 (2742.66ms, 357MB)
테스트 4 〉 통과 (2479.01ms, 418MB)
테스트 5 〉 통과 (5375.92ms, 786MB)반응형