문제 파악
각 문자열들을 비교했을때 다른문자열의 접두사가 있는지 없는지 판단하라.
index 0 → index2의 접두어다. 이런 문제이다.
접근 방법
사실 이 문제는 해쉬를 활용하면 쉽게 풀 수 있는 문제이다.
하지만 해쉬로 풀지 않는 이유는 더 빠르게 풀 수 있는 방법이 존재하기 때문이고 개념은 알아야하기 때문이다.
트라이는 문자열을 저장하는데 가장 적합화된 자료구조이다.
구현시간이 좀 많이 걸리고, 응용단계로가면 레벨이 많이 높다고 알고있기 때문에 개념을 잡는다는 느낌으로만 알고가자!
[”119”, ”2434”, ”11943”, ”24449”] 라는 배열이 주어진다고 생각해보자.
트라이 개념은 다음과 같다. E : 문자열의 끝이라고 생각하자.
119 저장 →
/**
root- 1
- 1
- 9
- E
*/
2434 저장 →
/** root- 1 2
- 1 4
- 9 3
- E 4
*/E
11943 저장 →
/**root- 1 2
- 1 4
- 9 3
- 4 4
- 3 E
- E
*/
24449 저장 →
/** root- 1 2
- 1 4
- 9 3 4
- 4 4 4
- 3 E 9
- E E
*/
설명에 앞서 일단 트리의 형태를 가지고 있고, 각 노드들은 연결되어있다.라고 알고가자.
그래서 이제 이 트라이 자료구조를. 활용을 해서 문제를 풀이할것이다.
접두어인지 확인하기 위해서 문자열의 끝을 살짝 변형해서 생각할것이다.
119 저장 →
/**
root- 1
- 1
- 9
- E
*/
현재 이 상태에서 11943을 저장할것이다.
2.1 11943 저장 →
/**
root- 1
- |
- 1
- |
- 9
- | \
- E 4
|3|
*/E
이런식으로 저장된다고 생각을해보면 11943을 저장할때, 119에서 가지가 한갈래 더 생기므로 접두어가 존재한다고 알 수 있다.
2.2 11 저장 →
/**
root- 1(o)
- 1(o)
- 9
- E
*/
11을 저장하면 이미 11보다 더 긴 문자열이 있는걸 알 수 있다. 따라서 11은 접두어라고 생각할 수 있다.
생각은 여기서 끝내고 어떤식으로 구현을 할 것인지 생각을 해보면
각 문자들을 노드라고 생각을 하면 , 각각의 노드는 자식을 가지고있다.
끝내는 조건은
자식이 두 갈래길로 갈라진다.
어떠한 문자열을 다 저장했을때, 자식이 더 남아있을때
코드 구현
import java.util.HashMap;
import java.util.Map;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Trie trie = new Trie();
for (int i = 0; i < phone_book.length; i++) {
if (!trie.insert(phone_book[i])) {
answer = false;
}
}
return answer;
}
static class Node{
Map<Character, Node> child = new HashMap<>();
boolean isEnd;
}
static class Trie{
Node root = new Node();
boolean insert(String word) {
Node currentNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (currentNode.child.get(c) == null) {
currentNode.child.put(c, new Node());
}
currentNode = currentNode.child.get(c);
if(currentNode.isEnd == true) return false;
}
if(currentNode.child.size() !=0) return false;
currentNode.isEnd = true;
return true;
}
}}
배우게 된 점
트라이는 공간복잡도를 상당히 잡아먹는 자료구조이다. 위 문제에서 트라이로 풀었을때의 시간복잡도는
O(n+m)이 나온다. n은 배열원소 개수이고 m은 문자열 길이다.
