[프로그래머스][KAKAO_BLIND][2018] 자동 완성

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict

def solution(words):
    answer = 0
    dic = defaultdict()
    for word in words:
        crnt = dic
        for c in word:
            if c not in crnt:
                crnt[c] = defaultdict()
                crnt[c]["cnt"] = 0
            crnt[c]["cnt"] += 1
            crnt = crnt[c]


    for word in words:
        crnt = dic
        for c in word:
            answer += 1
            if crnt[c]["cnt"] == 1:
                break
            crnt = crnt[c]

    return answer

• 트라이
  
  • 트라이 구조에서 각 문자를 지날 때마다 카운트
  • 카운트가 1인 경우 뒤에 올 문장을 예상할 수 있으므로 종료

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 트라이 구조로 간단히 풀 수 있다