프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://programmers.co.kr/learn/courses/30/lessons/17685
코딩테스트 연습 - [3차] 자동완성
자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g
programmers.co.kr
내가 작성한 코드
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
기억해야할 것
- 트라이 구조로 간단히 풀 수 있다
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_인턴][2021] 거리두기 확인하기 (0) | 2021.09.05 |
---|---|
[프로그래머스][KAKAO_인턴][2021] 숫자 문자열과 영단어 (0) | 2021.09.05 |
[프로그래머스][KAKAO_BLIND][2018] 셔틀버스 (0) | 2021.09.03 |
[프로그래머스][KAKAO_BLIND][2018] N진수 게임 (0) | 2021.09.03 |
[프로그래머스][KAKAO_BLIND][2018] 압축 (0) | 2021.09.03 |