[프로그래머스] - 전화번호 목록

문제

 

조건

 

입출력 예제

 

솔루션

• Trie (트라이) 자료구조를 사용한다.
  • 트라이 : https://soobarkbar.tistory.com/71?category=824429
  • Why 트라이 ?) 검색속도가 빠르기도 하고, 문자열의 끝을 알려주는 isEndofNumber를 통해 접두사인지를 확인할 수 있기 때문.

위 URL과의 차이점

1. TrieNode 클래스의 isExistedChildren() 함수.
2. Trie 클래스의 isPrefix(String key) 함수.

코드 설명

1. Trie 객체를 생성한다.
2. Trie에 입력으로 주어진 phone_book 문자열들을 모두 삽입한다 (Insert).
3. 모두 삽입된 Trie에 대해 다시 처음부터 phone_book의 문자열들에 대해 접두사 (Prefix) 인지 확인하는 작업 (isPrefix 함수) 을 수행한다.
   1. 만약 접두사라면, 정답 (answer) 을 false로 갱신하고 for 반복문을 빠져나온다.
   2. 접두사가 아니라면, 다음 문자열에 대해 동일하게 수행한다.
4. 모두 접두사가 아니라면, 기존 answer 값인 true를 반환한다.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_phonenumberlist.java

Trie를 구성하는 노드 객체를 만드는 TrieNode 클래스

 

boolean isExistedChildren()

• 해당 노드가 자식 노드를 가지고 있는지 확인하는 함수. (자식이 있다는 것은 해당 노드가 문자열의 끝부분이 아니라는 것)

 

 

 

Trie 트리 객체를 만드는 Trie 클래스

 

void Insert(String key)

• Trie 트리에 key 문자열을 삽입하는 함수.

 

boolean isPrefix(String key)

• key 문자열이 Trie 트리 내에서 접두사인지 확인하는 함수.

 

 

 

 

 

결과