[Python] 프로그래머스. 2020 카카오 recruit - 가사 검색 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

 

트라이 자료구조를 안 쓰고 푸는 법 / 트라이 사용해서 푸는 법 두 가지 다 시도해 봤다.

 

트라이를 안 쓰는 경우는 python string의 startswith, endswith 방법을 사용해서 풀 수 있지만, 효율성에서 통과를 못 한다.

 

트라이를 사용할 경우 이 문제에서 가장 어려웠던 건 '문자열 개수'를 반영하는 것이었다.

fro??일 경우 fro로 시작하면서 length가 5인, fro???는 length가 6인 걸 반환해야 하는데

fro까지 도착한 뒤, 아래 노드를 전부 순회하면 시간초과가 났다. 아마 노드를 순회하는 내 코드가 비효율적이어서 그런 것 같기도 한데..

 

내가 생각한 해결방법은, 매 노드마다 length라는 dict 변수를 두고, length 값만큼 더해주는 방식이었다. 즉 '문자열의 길이가 K이면서 해당 노드를 거쳐가는 문자열의 개수'를 생성하는 방식이다.

 

예컨대 frode를 입력받아 트라이에 저장할 때, o 노드에서 노드의 length 변수는 key 5 -> value 1을 가지고 있다.

front가 입력으로 들어오면, o 노드의 length 변수는 key 5 -> value 2로 업데이트된다.

 

결과적으로, prefix까지 도달한 다음 해당 노드의 length 변수에서 문자열 길이를 key값으로 입력해서 값을 반환받는 형태로 만들었다.

 

<문자열 함수를 사용한 solution>

 

	def solution(words, queries):
	result = []
	for query in queries:
	answer = 0
	length = len(query)
	# 맨 앞글자가 ?인 경우
	if query[0] == "?":
	# 문자열을 뒤집는다
	query = query[::-1]
	# 필요한 문자열만 취한 뒤 다시 뒤집는다
	prefix = query.split("?")[0][::-1]
	for value in words:
	# prefix가 0이면, 단어 길이만 같을 경우 전부 포함된다
	if len(prefix) == 0 and len(value) == length:
	answer += 1
	elif value.endswith(prefix) and len(value) == length:
	answer += 1
	result.append(answer)
	else:
	prefix = query.split("?")[0]
	for value in words:
	if len(prefix) == 0 and len(value) == length:
	answer += 1
	elif value.startswith(prefix) and len(value) == length:
	answer += 1
	result.append(answer)
	return result

view raw [프로그래머스] 가사 검색_without_trie.py hosted with ❤ by GitHub

 

<트라이 자료구조를 사용한 solution>

 

 

	# from itertools import chain
	from collections import defaultdict
	class Node:
	def __init__(self, char, length = None, data = None):
	self.char = char
	self.data = None
	self.children = {}
	# length값을 저장할 dictionary. 코드를 간소화하려고 defaultdict을 사용해
	# 인자값이 없으면 0을 리턴하도록 했다.
	self.length = defaultdict(int)
	class Trie:
	def __init__(self):
	self.head = Node(None)
	def insert(self, string):
	node = self.head
	node.length[len(string)] += 1
	for char in string:
	if char not in node.children:
	node.children[char] = Node(char)
	# children Node의 length 변수에 [문자열 길이] += 1을 해줬다.
	# 해당 노드를 거쳐가는 문자열 중 길이가 len(string)인 것의 개수를 저장한 것.
	node.children[char].length[len(string)] += 1
	node = node.children[char]
	node.data = string
	def start_with(self, prefix, length):
	node = self.head
	for char in prefix:
	if char in node.children:
	node = node.children[char]
	else:
	return 0
	# prefix의 마지막 노드에서 length변수를 확인해
	# 해당 노드를 거쳐간 문자열 중 길이가 length인 것의 개수를 반환한다.
	return node.length[length]
	def solution(words, queries):
	answer = []
	front = Trie()
	back = Trie()
	for word in words:
	front.insert(word)
	back.insert(word[::-1])
	for word in queries:
	# 전부 ?일 경우 - 문자열 길이만 일치하면 된다
	if word == "?"*len(word):
	answer.append(front.head.length[len(word)])
	# 맨 앞 글자가 ?인 경우는 역방향 트라이를 사용했다
	elif word[0] == "?":
	prefix = word[::-1].split("?")[0]
	answer.append(back.start_with(prefix, len(word)))
	else:
	prefix = word.split("?")[0]
	answer.append(front.start_with(prefix, len(word)))
	return answer

view raw [프로그래머스] 가사 검색_with_trie.py hosted with ❤ by GitHub

효율성 테스트 메모리 1.32GB.....

분명 더 효율적인 방식이 있지 않을까..?