알고스팟 문제 링크: https://algospot.com/judge/problem/read/SOLONG

 

algospot.com :: SOLONG

안녕히, 그리고 물고기는 고마웠어요! 문제 정보 문제 문자 입력이 불편한 핸드폰이나 타블렛 같은 기계에서는 빠른 타이핑을 위해 강력한 자동 완성 기능을 제공합니다. 시리우스 사이버네틱

algospot.com

사전에 들어있는 단어들이 빈도수와 함께 주어진다. 특정한 문장을 완성시키려할때 탭키를 사용하여 사전을 참조한 자동완성 기능을 사용할 수 있다.

타이핑한 알파벳을 접두사로 갖는 단어들의 빈도수를 우선순위로 하고 빈도수가 같은  단어가 두개 이상있으면 사전순을 우선순위로 한다.

이때 특정한 문장을 완성시키기 위한 총 타이핑 횟수를 구하는 문제이다.

 

일단 사전에 들어갈 문자들을 트라이 형태로 삽입한다. 이때 삽입하는 단어들을 빈도수와 사전순을 고려하여 정렬한 후 차례로 삽입한다.

이런식으로 삽입할 경우 자동완성을 위한 first를 한번만 갱신하면 되므로 자동완성 단어를 계산하기 위한 메모리와 시간이 최소화 된다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/solong.cpp

 

GitHub - sbl133/JongmanBook

Contribute to sbl133/JongmanBook development by creating an account on GitHub.

github.com

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

+ Recent posts