[프로그래머스] 자동완성 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

 

백준의 휴대폰 자판과 거의 비슷하다.

https://westmino.tistory.com/140

[BOJ/백준] 5670 휴대폰 자판 파이썬

 

휴대폰 자판 문제는 모든 단어에 대해서 tri를 탐색했다면 이번 문제는 루트에서 각 노드를 한번씩만 탐색하는거로 했다.

 

그래서 각 노드에 count라는 변수를 하나더 추가 했다.

이것은 해당 글자까지 들어온 단어의 개수를 표시한다.

예를 들어

abc

abd

두 개의 단어가 왔다면

a : 2

b : 2

c : 1

d : 1

의 값을 가질 것이다.

 

그래서 이것을 자동완성시켜서 나갈지 아니면 계속 탐색할지에 활용 했다.

만약 count가 1이라면 해당 글자를 포함한 단어는 하나밖에 없다는 것이므로 자동완성하면 되서 더이상 입력이 필요가 없다.

 

그래서 count와 is_end 변수를 활용하여 tri를 순회하면서 입력 횟수를 카운팅 했다.

 

class Node:
    def __init__(self,alpha):
        self.alpha = alpha
        self.child = []
        self.count = 0
        self.is_end = False
        
def solution(words):
    global answer
    answer = 0
    tri = make_tri(words)
    
    travel_tri(tri,0)
    return answer

def travel_tri(now, count):
    global answer
    if now.is_end:
        answer += count
    elif now.count == 1:
        answer += count
        return
    
    for child in now.child:
        travel_tri(child, count+1)
def make_tri(words):
    tri = Node('-')
    
    for word in words:
        now = tri
        for alpha in word:
            now = search_child(now, alpha)
        now.is_end = True
        
    return tri
def search_child(now, target):
    for child in now.child:
        if child.alpha == target:
            child.count += 1
            return child
    node = Node(target)
    node.count = 1
    now.child.append(node)
    return node