class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Trie trie = new Trie();
for (String phone : phone_book) {
if (!trie.insert(phone)) {
answer = false;
break;
}
}
return answer;
}
}
class Node {
boolean exist;
Node[] child;
Node() {
exist = false;
child = new Node[10];
}
}
class Trie {
Node root;
Trie() {
root = new Node();
}
boolean insert(String phone) {
int length = phone.length();
Node node = root;
for (int i = 0; i < length; i++) {
int num = phone.charAt(i) - '0';
if (node.child[num] == null) {
node.child[num] = new Node();
}
else {
if (i == length - 1) return false;
}
node = node.child[num];
if (node.exist) return false;
}
node.exist = true;
return true;
}
}
문제를 보자마자 트라이가 생각나서 트라이로 풀었는데
다른 사람의 풀이를 보니 그냥 쉽게 생각하면 되는 문제였다.
수가 적어서 이중 for문을 돌려도 효율성을 통과하나보다.
해시 문제였는데 해시를 어떻게 써먹어야할지는 아직 잘 모르겠다.
다른 사람의 풀이를 통해 startsWith라는 메소드에 대해 새롭게 알게되었다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges