프로그래머스 - [3차] 자동완성 [2018 KAKAO BLIND RECRUITMENT]

문제 설명:

자동완성
포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go
gone
guild
go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

---

문제 예시:

words	result
["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

---

문제 해결:

def solution(words):
    answer = 0
    N = len(words)
    MAXLEN = len(max(words, key=lambda x: len(x)))
    
    # 반드시 시작점부터 idx까지
    # key값으로 넣고 count 값 넣어서 1인 애들만 더하기
    idx = 1
    count = 0
    
    for idx in range(1, MAXLEN+1):
        lst = []
        dictWords = {}
        
        for idxw in range(len(words)):
            target = words[idxw][:idx]
            if target not in dictWords.keys():
                dictWords[target] = [idxw]
            else:
                dictWords[target].append(idxw)
                
            if len(words[idxw]) == idx:
                count += 1
                answer += len(words[idxw])
                
                if words[idxw] not in lst:
                    lst.append(words[idxw])
        
        for k, v in dictWords.items():
            if len(v) == 1:
                if words[v[0]] not in lst:
                    lst.append(words[v[0]])
                    count += 1
                    answer += len(k)
        
        for i in lst:
            words.remove(i)
        
        if count == N:
            break
    
    return answer

제일 처음으로 아무 생각없이 구현만 해보았다.

시간 초과로 인해 코드를 다시 작성해야 했다.

문제점은 이미 answer에 확정된 단어를 다시 보고 있는 것이 문제였고 끝났음에도 for문을 계속 도는 것이 문제였다.

 

def solution(words):
    # 트라이(Trie) 구조 생성
    # 구조: {문자: [해당 문자를 거쳐가는 단어 수, 하위 노드 딕셔너리]}
    trie = {}
    
    # 1. 모든 단어를 트라이에 삽입
    for word in words:
        current_node = trie
        for char in word:
            if char not in current_node:
                current_node[char] = [0, {}]
            current_node[char][0] += 1 # 이 노드를 거쳐가는 단어 수 증가
            current_node = current_node[char][1]
            
    answer = 0
    
    # 2. 각 단어별 최소 입력 횟수 계산
    for word in words:
        current_node = trie
        count = 0
        for char in word:
            count += 1
            # 만약 이 접두사를 공유하는 단어가 1개뿐이라면 중단
            if current_node[char][0] == 1:
                break
            current_node = current_node[char][1]
        answer += count
        
    return answer

다음에서 사용한 로직은 트라이(trie)이다. 

 

이 로직은 처음에 {} 으로 비어있는 dict를 주면서 그 이전에 거쳐간 알파벳이 없다는 것을 인지 시키는 것이 제일 중요하다

따라서, gone이라면 {g}, [1, {go}], ... [1, {gone}] 이 된다.

이렇게 모든 단어에 대해서 모든 char를 돌고 결과값을 낸다

 

#2 에서는 만들어진 trie를 통해 1만 나오는 값을 찾고 해당 값을 answer에 더하고 return한다