2017 kakao blind recruitment 3차 자동완성

from collections import defaultdict
def solution(words):
    answer = 0
    duplicatedict = defaultdict(int)
    subwordlist = [[word[:idx] for idx in range(1, len(word)+1)] for word in words]
    for idx, word in enumerate(words):
        for sw in subwordlist[idx]:
            duplicatedict[sw] += 1
        
    for word in words:
        searchnum = sum([ 1 for idx, w in enumerate(word) if duplicatedict[word[:idx+1]] > 1]) + 1
        searchnum = min(len(word), searchnum)
        answer += searchnum
        
                
    return answer

정확성: 81.8

합계: 81.8 / 100.0

 

시간초과로 실패한 문제 4개

 

from collections import defaultdict
def solution(words):
    answer = 0
    words.sort(reverse = True)
    
    for idx, word in enumerate(words):
        if idx == 0:
            nextword = words[idx+1]
            searchnum = sum([1 for jdx, _ in enumerate(word) if word[:jdx+1] == nextword[:jdx+1]])+1
            answer += min(searchnum, len(word))
        elif idx == len(words)-1:
            prevword = words[idx-1]
            searchnum = sum([1 for jdx, _ in enumerate(word) if word[:jdx+1] == prevword[:jdx+1]])+1
            answer += min(searchnum, len(word))
        else:
            prevword = words[idx-1]
            nextword = words[idx+1]
            searchnum = max(sum([1 for jdx, _ in enumerate(word) if word[:jdx+1] == nextword[:jdx+1]])+1, \
                            sum([1 for jdx, _ in enumerate(word) if word[:jdx+1] == prevword[:jdx+1]])+1)
            answer += min(searchnum, len(word))
                
    return answer

sort한 뒤 인접한 문자열만을 비교

해설을 보고 풀었다는 게 아쉽다...

 

trie 구조를 사용해서 푸는 방식도 있었다.