BAEKJOON 14426번: 접두사 찾기 (feat. Trie)

https://www.acmicpc.net/problem/14426

14426번: 접두사 찾기

들어가며..

이 포스팅에서 사용할 풀이는 해당 문제의 정해가 아닐 수 있다.

 

풀이

먼저, 트라이(Trie)는 문자열을 저장하고 검색하기 위한 자료구조로, 트라이에 저장된 모든 문자열은 만약 서로의 공통 접두사가 있을 때, 해당하는 노드들을 공유한다.

오른쪽의 그림은 트라이를 나타낸 그림이다. 그림을 보면 바로 이해가 될 듯 하다.

 

문제로 돌아와 보자. N개의 문자열로 이루어진 집합 S의 어떤 문자열이든 간에 하나의 문자열의 접두사이기만 하다면, count해주면 된다. 이는 트라이를 통해 쉽게 해결할 수 있다. 그냥 입력 받는 문자열을 트라이에서 Search 해주고, 그 문자열이 있다면 count, 아니면 그냥 넘어가면 된다. 즉, 해당 문자열 전체와 같은 경로가 있는지 확인하면 된다.

 

https://github.com/P4rkingZ0eN/Well_Known/blob/main/Simple_Trie.cpp

위 링크는 필자가 구현한 트라이이다. (문제의 정답이 되는 코드는 아니다.)

string S;
//임의의 문자열 S가 있다고 하자.

Search(1,0)
// S가 Trie에 포함되어 있으면 true를 그렇지 않으면 false를 return한다.

Insert(1,0)
// S를 Trie에 추가한다.