Algorithm/문자열

BOJ#5052 전화번호 목록

밤이2209 2017. 11. 25. 16:32

BOJ#5052 전화번호 목록


* 문제



* 풀이

저는 이 문제를 Trie를 이용해서 풀어보았습니다.

Trie를 처음 공부하고 풀어보는 것이라서 부족한점이 있을 것 같습니다. 댓글로 알려주시면 감사하겠습니다.

,

1. 일단 전화번호 목록을 배열에 저장한 후 정렬을 진행합니다.
2. Trie 자료구조에 Insert합니다.
3. 이 과정에서 terminal 노드인데 children이 추가되는 경우 '일관성 있지 않은' 목록으로 판단합니다.



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int T = Integer.parseInt(br.readLine());

while (T-- > 0) {

int n = Integer.parseInt(br.readLine());
String[] num = new String[n];

Trie trie = new Trie();
boolean ret = true;

for (int i = 0; i < n; i++) {

num[i] = br.readLine();
}

Arrays.sort(num);

for (int i = 0; i < n; i++) {

if (!trie.insert(num[i])) {

ret = false;
break;
}
}

System.out.println(ret ? "YES" : "NO");
} // ~ test case loop
}
}

class Trie {

private TrieNode root;

Trie() {

root = new TrieNode();
}

private int toNumber(char c) {

return c - '0';
}

boolean insert(String key) {

TrieNode currentNode = root;
int length = key.length();

for (int i = 0; i < length; i++) {

char c = key.charAt(i);
int next = toNumber(c);

if (currentNode.children[next] == null) {

currentNode.children[next] = new TrieNode();
}

currentNode = currentNode.children[next];

if (currentNode.isTerminal && i + 1 < length) {

return false;
}
}

currentNode.isTerminal = true;

return true;
}
}

class TrieNode {

TrieNode[] children = new TrieNode[10];
boolean isTerminal;

TrieNode() {

isTerminal = false;

for (int i = 0; i < 10; i++) {

children[i] = null;
}
}
}


'Algorithm > 문자열' 카테고리의 다른 글

BOJ#5670 휴대폰 자판  (0) 2017.11.26
BOJ#1152 단어의 개수  (0) 2017.05.22
BOJ#1254 팰린드롬 만들기  (0) 2017.03.31
BOJ#10942 팰린드롬?  (0) 2017.03.30