[3차] 자동완성

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

프로그래머스

---

1차 시도

구현부터 해보자는 생각에 먼저 words를 돌면서 word가 완성될 수 있는 모든 경우의 수에 대한 딕셔너리를 만들었습니다.

ex) words = ["go", "gone"]는 {"g": ["go", "gone"], "go": ["go", "gone"], ":gon": ["gone"], "gone": [ "gone" ]}

딕셔너리를 만든 후 words를 돌아서 특정 word가 만들어 지는 경우의 수 key에 대해 특정 word value를 가지거나 완전한 word만 가능할 때 answer에 key의 길이를 더해주면 될 것 같다고 생각했습니다.

from collections import defaultdict

def solution(words):
    answer = 0
    
    word_dict = defaultdict(list)
    
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            word_dict[word[:i]] += [word]
            
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            if len(word_dict[word[:i]]) == 1:
                answer += i
                break
        else:
            answer += N
    
    return answer

정확성: 81.8

합계: 81.8 / 100.0

 

2차 시도

value에 가능한 word 리스트가 아닌 개수를 넣어서 len(word_dict[word[:i])의 시간을 줄여보려했습니다.

또한 먼저 word_dict[word]가 1가 아니라면 바로 answer에 word 길이를 더하여 word에 대해 for문이 도는 횟수를 줄이고자 했습니다.

from collections import defaultdict

def solution(words):
    answer = 0
    
    word_dict = defaultdict(int)
    
    for word in words:
        N = len(word)
        for i in range(1, N+1):
            word_dict[word[:i]] += 1
            
    for word in words:
        N = len(word)
        if word_dict[word] != 1:
            answer += N
            continue
        for i in range(1, N+1):
            if word_dict[word[:i]] == 1:
                answer += i
                break
    
    return answer

정확성: 81.8

합계: 81.8 / 100.0

 

※ 실행 결과

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.1MB)
테스트 6 〉	통과 (740.89ms, 115MB)
테스트 7 〉	통과 (0.02ms, 9.93MB)
테스트 8 〉	통과 (767.83ms, 115MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.02ms, 9.96MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (669.38ms, 115MB)
테스트 13 〉	통과 (695.28ms, 115MB)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	통과 (0.02ms, 10.3MB)
테스트 16 〉	통과 (627.05ms, 115MB)
테스트 17 〉	통과 (687.17ms, 115MB)
테스트 18 〉	통과 (0.03ms, 10MB)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	통과 (578.32ms, 115MB)
테스트 21 〉	실패 (시간 초과)
테스트 22 〉	실패 (시간 초과)

 

다른 사람 코드

class Node(object):
    def __init__(self, key, cnt = 0):
        self.key = key
        self.cnt = cnt
        self.child = {}

class Trie():
    def __init__(self):
        self.head = Node(None)
    def insertTree(self, string):
        cur = self.head
        for token in string:
            if token not in cur.child:
                cur.child[token] = Node(token)
            cur = cur.child[token]
            cur.cnt += 1
    def searchTree(self, string):
        cur = self.head
        cnt = 0
        for token in string:
            cnt += 1
            cur = cur.child[token]
            if cur.cnt == 1:
                return cnt
        return len(string)   

def solution(words):
    answer = 0
    wordTree = Trie()
    for word in words:
        wordTree.insertTree(word)
    for word in words:
        answer += wordTree.searchTree(word)
    return answer

정확성: 100.0

합계: 100.0 / 100.0

 

※ 실행 결과

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (2663.90ms, 275MB)
테스트 7 〉	통과 (0.03ms, 10.1MB)
테스트 8 〉	통과 (2793.23ms, 275MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.03ms, 10.2MB)
테스트 11 〉	통과 (0.03ms, 10.1MB)
테스트 12 〉	통과 (2572.36ms, 275MB)
테스트 13 〉	통과 (2508.36ms, 275MB)
테스트 14 〉	통과 (2154.72ms, 398MB)
테스트 15 〉	통과 (0.02ms, 10.2MB)
테스트 16 〉	통과 (2154.92ms, 275MB)
테스트 17 〉	통과 (2227.31ms, 275MB)
테스트 18 〉	통과 (0.03ms, 10.3MB)
테스트 19 〉	통과 (2133.43ms, 398MB)
테스트 20 〉	통과 (2295.83ms, 275MB)
테스트 21 〉	통과 (2349.56ms, 398MB)
테스트 22 〉	통과 (1981.25ms, 398MB)

 

풀이

Trie 알고리즘으로 푼 코드입니다.

단어 단위로 트리 형식으로 연결합니다.

트리의 깊이가 단어의 길이가 됩니다.

이 코드에서 노드의 구조는 key(단어의 token), cnt(자식 노드 수), child(자식 노드들)로 구성되어 있습니다.

여기서 child는 딕셔너리 형식으로 상수 시간에 검색하도록 합니다.

해당 단어의 자동 완성 조건에 만족하려면 노드의 cnt가 1일 때까지 타고 들어가거나, 노드의 cnt가 1인 경우가 없어서 모든 노드를 타고 들어가야합니다.

 

궁금한 점

2차 시도에서 짠 코드의 실행 결과에서 통과된 시간을 보면 3배이상 빠른데, 시간 초과는 어떤 경우에서 뜨는지 모르겠습니다.

혹시 아시는 분은 댓글로 알려주시면 감사하겠습니다.