프로그래머스. 자동완성

티스토리 뷰

tose33 2022. 2. 22. 21:19

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

자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g

programmers.co.kr

이 문제를 계기로 트라이 자료구조를 공부해봤다.

트라이 자료구조

https://yabmoons.tistory.com/379 [ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++) 이번 글에서는 자료구조 트라이(TRIE) 에 대해서 알아보자. 1. 트라이 (TRIE) ?? 먼저 '트라이'가 무엇인지에 대해서 부터 알..

tose33.tistory.com

트라이 자료구조를 그대로 구현하면 되는데 다른점은,

노드를 Insert하면서 각 노드를 방문할때 각 노드에 child 변수를 1씩 증가시킨다.

이렇게 함으로서 모든 문자열들을 트라이에 삽입했을때 각 노드가 몇번 방문되었는지 기록되고,

child 변수의 의미는 현재 노드 아래로 존재하는 문자열의 갯수가 된다.

즉 child 변수가 1인 노드라면 더이상 자식 노드로 진행할 필요 없이 자동완성 된다는 뜻이 된다.

백준 11758. CCW (0)	2022.02.24
백준 1011. Fly me to the Alpha Centauri (0)	2022.02.24
백준 1913. 달팽이 (0)	2022.02.19
프로그래머스. 블록 게임 (0)	2022.02.19
프로그래머스. 무지의 먹방 라이브 (0)	2022.02.16

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함