(JAVA) 백준 5052번 : 전화번호 목록 --- [트라이]

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

안녕하세요.

 

문자열 탐색을 위한 알고리즘으로 트라이 알고리즘을 사용했습니다.

 

트라이 알고리즘은 노드로 이루어진 트리를 사용하는 방법인데요.

 

 

가장 긴 문자열의 길이가 L, 총 문자열들의 수를 M개 라고 할 때

  -  삽입 : 1개 넣을 시 O(L)  ///  M개 넣을 시 : O(M*L)

  -  탐색 : 1개 탐색 시 O(L)  ///  M개 탐색 시 : O(M*L)

 

 

O(NlogN) 이 소모되는 이분탐색보다도 빠른 알고리즘 입니다.

 

더 세부적인 설명과 정보는 다른 포스팅에서 다루겠습니다.

 

 

이 문제는 간단합니다.

트라이 객체에 모든 입력받은 문자열을 넣고

 

문자열 한 개씩 contain(포함) 되어있는지 판별하면 됩니다.

 

 

단, 주의하실 점은

 

999999

9

 

와 

 

9

999999

 

전부 접두사가 겹치는 경우 입니다.

 

 

궁금하신 사항은 하단 소스코드 참고하시고 댓글 적어주시면 감사하겠습니다.

 

감사합니다.

 

 

 

소스코드

---