[Python] 프로그래머스. 2018 카카오 recruit - 자동완성 (Level 4)

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

코딩테스트 연습 - [3차] 자동완성 | 프로그래머스

트라이 자료구조의 활용을 의도한 문제.

 

트라이 자료구조의 의미와 Python 구현 방법은 https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

파이썬에서 Trie (트라이) 구현하기

에서 확인할 수 있다. Trie의 구현 방법도 이 포스트를 참고했다.

---

풀이의 핵심은 '더 이상 단어의 분기점이 없는 지점'을 찾는 것.

문제의 예시대로 설명하자면

 

1. go를 트라이 자료구조에 입력한다. 먼저 g라는 노드가 생성되고, 해당 노드 뒤에 o라는 노드가 생성되어야 한다.

g라는 노드를 생성하면, 노드 안에 possible_word라는 변수가 0으로 초기화되어 있다. 값을 1 더해준다.

o라는 노드도 마찬가지로, 생성한 다음 possible_word라는 변수에 1 더해준다.

 

이 상태에서는 'g'라는 단어가 주어졌을 때 만들 수 있는 단어의 개수는 1개다. 'go' 라는 단어. 'o'라는 단어도 마찬가지다.

즉 g나 o라는 단어의 possible_word 변수 값은 1이다.

 

2. gone이 입력으로 들어온다.

먼저 g를 입력으로 받는다. g라는 노드가 이미 있으므로, possible_word 변수에 1을 더해준다.

다음 o 변수도 마찬가지로, possible_word 변수에 1을 더해준다.

이제 n이라는 변수가 들어온다. 단어 n을 가진 노드는 아직 없으니, n 노드를 생성한 다음 o 노드 뒤에 n 노드를 연결해 준다.

새로 생성한 노드이므로 possible_word 값은 0으로 초기화되어 있다. 이 값에도 1 더해주자.

 

이런 식으로 진행하면, 'g'라는 단어의 possible_word는 2, 'o'라는 단어의 possible_word도 2, 'n'의 possible_word는 1이 된다.

 

만약 gone을 찾아야 하면, g -> o -> n 순서대로 트라이를 순회하면서 possible_word 값이 1일 때까지 확인하면 된다.

1이면 그 밑으로는 더 볼 필요가 없게 된다.

 

go를 찾아야 할 경우, o까지 찾았는데 possible_word가 2이다. 이럴 때는 그냥 'go'라는 단어 길이를 더해주면 된다.

 

로직을 구현한 코드는 아래와 같다.

 

 

 

	class Node:
	def __init__(self, char, data = None):
	# 노드의 글자
	self.char = char
	# 마지막 노드일 때 string 값
	self.data = data
	# 해당 노드를 거쳐갈 경우 가능한 글자의 개수
	self.possible_word = 0
	# trie의 자식 노드들
	self.children = {}
	class Trie:
	def __init__(self):
	self.head = Node(None)
	def insert(self, string):
	curr_node = self.head
	for char in string:
	# 노드의 가능한 글자 개수를 1 늘려준다.
	curr_node.possible_word += 1
	if char not in curr_node.children:
	# 해당 노드의 next에 문자열이 등록되어 있지 않으면 등록한다
	curr_node.children[char] = Node(char)
	# 다음 노드로 이동한다.
	curr_node = curr_node.children[char]
	# 마지막 글자. 마지막 글자의 possible_word도 1로 만들어준다.
	curr_node.possible_word += 1
	# 마지막 글자이므로, 해당 trie를 타고 왔을 때의 최종문자를 저장해둔다.
	curr_node.data = string
	def search(self, string):
	curr_node = self.head
	for char in string:
	# 노드를 타고 내려간다.
	if char in curr_node.children:
	curr_node = curr_node.children[char]
	else:
	return False
	# 해당 노드까지 왔을 때 만들 수 있는 문자의 개수가 1이면 True 반환
	if curr_node.possible_word == 1:
	return True
	else:
	return False
	# not_used
	def start_with(self, prefix):
	curr_node = self.head
	result = []
	for char in prefix:
	if char in curr_node.children:
	curr_node = curr_node.children[char]
	subtrie = curr_node
	else:
	return []
	# 노드들
	stack = list(subtrie.children.values())
	# dfs로 단어 완성
	while stack:
	node = stack.pop()
	if node.data != None:
	result.append(node.data)
	stack.extend(list(node.children.values()))
	return result
	def solution(words):
	cnt = 0
	word_trie = Trie()
	for word in words:
	word_trie.insert(word)
	for word in words:
	# 단어 끝까지 돌았는데
	# possible_word가 1이 아닌 경우를 확인하는 변수
	already_find = False
	for i in range(1, len(word)+1):
	if word_trie.search(word[:i]):
	cnt += len(word[:i])
	already_find = True
	break
	if not already_find:
	cnt += len(word)
	return cnt

view raw [프로그래머스] 자동완성.py hosted with ❤ by GitHub