문제 링크
조건
- n개의 전화번호 목록 중 임의의 두 번호가 서로 접두사 관계에 있다면 NO (일관성 없음), 없다면 YES (일관성 있음) 출력
접근 방법
- 정렬
- 전화번호 목록 문자열 정렬 후 바로 앞 번호가 현재 번호의 접두사인지 확인
- n이 크지 않아서 정렬로 푸는게 속도나 메모리에 더 효율적임
- 트라이
- 전화번호를 하나씩 Trie 트리에 넣으면서 임의의 두 번호가 서로 접두사 관계에 있는지 확인
솔루션
public class Main {
static int t,n;//testcase, 전화번호 개수
static class Node{
Map<Character, Node> children;
boolean end;//끝번호인지 확인
Node(){
children = new HashMap<Character, Node>();
end = false;
}
}
static Node head;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine().trim());
top:
while(t-- > 0) {
head = new Node();
n = Integer.parseInt(br.readLine().trim());
while(n-- > 0) {
if(!InsertTrie(br.readLine().trim())) { => false면 일관성 X
while(n > 0) {//나머지 입력 받아서 버림
br.readLine();
n--;
}
System.out.println("NO");
continue top;
}
}
System.out.println("YES");
}
}
private static boolean InsertTrie(String number) {
Node tmp = head;
int len = number.length();
for(int i = 0; i < len; i++) {
char ch = number.charAt(i);
Node child = tmp.children.get(ch);
if(child == null) {//아직 만들어지지 X
tmp.children.put(ch, new Node());
child = tmp.children.get(ch);
if(i == len-1) {//마지막 문자인지 확인
child.end = true;
}
}else {
if(child.end || i == len - 1) return false;//이미 있는 번호 => 일관성 X
}
tmp = child;//다음 문자로 넘어감
}
return true;//일관성 있음(겹치지X)
}
}
리뷰