알고스팟 문제 링크: https://algospot.com/judge/problem/read/SOLONG
사전에 들어있는 단어들이 빈도수와 함께 주어진다. 특정한 문장을 완성시키려할때 탭키를 사용하여 사전을 참조한 자동완성 기능을 사용할 수 있다.
타이핑한 알파벳을 접두사로 갖는 단어들의 빈도수를 우선순위로 하고 빈도수가 같은 단어가 두개 이상있으면 사전순을 우선순위로 한다.
이때 특정한 문장을 완성시키기 위한 총 타이핑 횟수를 구하는 문제이다.
일단 사전에 들어갈 문자들을 트라이 형태로 삽입한다. 이때 삽입하는 단어들을 빈도수와 사전순을 고려하여 정렬한 후 차례로 삽입한다.
이런식으로 삽입할 경우 자동완성을 위한 first를 한번만 갱신하면 되므로 자동완성 단어를 계산하기 위한 메모리와 시간이 최소화 된다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/26.%20Trie/solong.cpp
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
algospot 감시 카메라 설치(문제 ID: GALLERY) c++ (0) | 2022.03.03 |
---|---|
algospot 보안종결자(문제 ID: NH) c++ (0) | 2022.03.01 |
algospot 신호 라우팅 (문제 ID: ROUTING) c++ (0) | 2021.10.29 |
algospot 하노이의 탑 (문제 ID: HANOI4B) c++ (0) | 2021.10.29 |
algospot 어린이날 (문제 ID: CHILDRENDAY) c++ (0) | 2021.10.28 |