[Java] BOJ5052, 백준 - 전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

트라이를 활용하여 풀 수 있다.

트라이에 삽입할 때 비교해주면 쉽게 풀 수 있음

 

트라이에 삽입할 때

1. 삽입 중간에 end node를 만날 경우

예를 들어 911 91111 순으로 삽입한다고 하면

91111을 삽입할 때 91111에서 이전에 삽입한 911의 end node를 만날 것이다.

이 경우 일관성 없음: false를 return해준다.

for (int i = 0; i < str.length(); i++) {
	node = node.childNode.computeIfAbsent(str.charAt(i), key -> new Node());
	if (node.end)
		return false;
}

 

2. 끝까지 다 넣었는데 다음에 이어지는 문자열이 있을 경우

예를 들어 91111 911 순으로 삽입한다고 하면

911의 삽입이 끝났는데, 911의 childNode가 null이 아니기 때문에 뒤에 더 이어져있는것임 > 일관성 없음 : return false

if (node.childNode.get(str.charAt(str.length() - 1)) != null)
	return false;

 

시간복잡도는

문자열의 최대길이: 10, 전화번호의 수 10000

10*10000 = 100000

 

참고로 중간에 일관성없는 전화번호임을 발견하더라도 continue 등을 이용해 다음 testcase로 넘어가지 않고 flag를 사용해주는 이유는 현재  testcase의 입력을 다 받지 않은채로 다음 testcase로 넘어가면 이전 테케 입력정보랑 충돌되서 데이터가 제대로 입력안되기 때문임.

값이 제대로 계산안되거나 문자열의 길이 차이로 인해서 NullPointerException 발생 가능

 

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int tc = 0; tc < TC; tc++) {
			int n = Integer.parseInt(br.readLine());
			boolean flag = false;
			Trie trie = new Trie();
			for (int i = 0; i < n; i++) {
				String str = br.readLine();
				if (!trie.insert(str))
					flag = true;
			}

			if (flag)
				System.out.println("NO");
			else
				System.out.println("YES");
		}
	}
}

class Trie {
	Node root = new Node();

	boolean insert(String str) {
		Node node = this.root;

		for (int i = 0; i < str.length(); i++) {
			node = node.childNode.computeIfAbsent(str.charAt(i), key -> new Node());
			if (node.end)
				return false;
		}
		if (node.childNode.get(str.charAt(str.length() - 1)) != null)
			return false;
		node.end = true;
		return true;
	}
}

class Node {
	Map<Character, Node> childNode = new HashMap<>();
	boolean end;
}