PY-L4-011 / 고급 자료구조
트라이 접두어 탐색
고급문제
소문자 단어 리스트 words와 접두어 prefix를 받습니다. 접두어로 시작하는 서로 다른 단어를 사전순 반환하세요. 트라이를 직접 구성해 보세요.
solve(*args) 함수에서 값을 반환하세요. print 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: [["cat","car","dog","car"],"ca"] 반환: ["car","cat"]
예제 2
입력: [["a","ab"],"a"] 반환: ["a","ab"]
힌트
단어 종료 표시를 자식 문자와 구별하세요.
해설·정답 보기
접두어 경로까지 이동한 뒤 하위 트라이를 사전순 순회합니다. 같은 단어는 종료 표시 하나로 합쳐집니다.
def solve(words, prefix):
root = {}
for word in words:
node = root
for ch in word:
node = node.setdefault(ch, {})
node[''] = True
node = root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
result = []
def visit(branch, text):
if '' in branch:
result.append(text)
for ch in sorted(k for k in branch if k != ''):
visit(branch[ch], text + ch)
visit(node, prefix)
return resultsolution.py결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.