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

문제

프로그래머스-전화번호 목록
전화번호부에 적힌 전화번호 중에서 한 번호가 다른 번호의 접두어인 경우가 있는지 판단하는 문제

• 예시 1
  119, 97674223, 11995524421 같이 번호가 있다면,
  세번째 번호인 11995524421는 첫번째 번호인 119가 접두사이므로 false이다

• 예시 2
  123, 456, 789 한 번호가 다른 번호의 접두사인 경우가 없으므로 true이다

풀이

1) Trie자료구조 형태를 만든다.
root로 사용할 Trie 클래스와 노드를 구성할 TrieNode 클래스를 생성했다.

• Trie 클래스
  TrieNode객체를 멤버변수로 가지고 있다.
• TrieNode 클래스
  HashMap<Character, TrieNode>,
  글자 마지막여부 판단을 위한 isEndWord를 가지고있다.

2) 전화번호들을 담은 배열 phone_book을 반복하면서 root에 저장하고 이 과정에서 true / false를 확인한다.
true -> 진행한다. 반복을 끝날때 까지 false가 리턴되지않았다면 true를 리턴한다
false -> 더이상 진행할 필요가 없으므로 false리턴 후 종료

2-1) 저장하는 함수(insert)
글로 풀어쓰는 설명이 너무 어려워서 그림을 그려보았는데..

(마우스 오른쪽 - 새 탭에서 이미지 열기)

축소판 트라이트리라고 생각하면 될 듯 ~!

소스코드

class Solution {
   public boolean solution(String[] phone_book) {
		Trie root = new Trie();

		for (int i = 0; i < phone_book.length; i++) {
			if (!root.insert(phone_book[i])) {
				return false;
			}
		}
		return true;
	}
}

class Trie {
	TrieNode root = new TrieNode();
	public boolean insert(String str) {
		TrieNode current = root;
		for (int i = 0; i < str.length(); i++) {
			if (current.children.containsKey(str.charAt(i))) {
				current = current.children.get(str.charAt(i));
				if (current.isEndWord)
					return false;
			} else {
				current.children.put(str.charAt(i), new TrieNode());
				current = current.children.get(str.charAt(i));
			}
		}
		// 4321등록되어있고 432를 insert하는 경우를 위한 접두사 확인 부분
        if(current.children.size()>0)
			return false;
		current.isEndWord = true;
		return true;
	}
}

class TrieNode {
	boolean isEndWord;
	HashMap<Character, TrieNode> children=new HashMap<>();
}