-
2020 KAKAO BLIND RECRUITMENT 가사 검색코딩 테스트/Level 4 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)
반응형