문제

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

---

입력

• 첫째 줄에 테스트 케이스의 개수 t가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다.
• 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다.

---

출력

• 각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

---

풀이

제한조건

• (1 ≤ t ≤ 50)
• (1 ≤ n ≤ 10000)
• 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

접근방법

Trie

Trie 구조의 변형으로 해결 할 수 있다.
(Trie 구조 : https://velog.io/@hyeokkr/Trie)

Trie 구조와 동일하게 구성을 한다.
다만, insert 과정에서 last 문자열을 만나면, 접두어인 경우가 발생하는 것이므로 일관성이 없는 것이다.

예시를 살펴보자.

3
911
97625999
91125426

(빨간원 : Last)
Trie구조로 본다면 처음 입력에 의해 구조가 그림과 같이 잡힌다.

이제 두 번째 숫자가 입력된다면 아래와 같이 된다

두 번째 입력까지도 Trie 구조 생성과정에서 Last를 만나지 않는다.

하지만 세 번째 입력은 문제가 발생한다.

숫자를 입력하는 과정에서 Last를 만나게 된다.
이는 곧 접두어를 가지게 되는 경우로 일관성이 깨지게 된다.

위와 같은 식으로 insert시 last를 만나는지의 여부에 따라 확인이 가능하다.

주의
길이가 짧은 수 부터 먼저 삽입하는것이 좋다.
짧은 수를 나중에 Trie에 insert 한다면, 접두어를 확인하는 과정에 문제가 발생한다.
한 번 생각해보자.. 어떤 문제가 발생할까..

---

코드

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

public class Main {
	static int T, N;

	static class TrieNode {
		private Map<Character, TrieNode> childNodes = new HashMap<>();
		private boolean isLast;

		public Map<Character, TrieNode> getChildNodes() {
			return childNodes;
		}

		public boolean isLast() {
			return isLast;
		}

		public void setLast(boolean last) {
			isLast = last;
		}
	}

	static class Trie {
		private TrieNode root;

		Trie() {
			root = new TrieNode();
		}

		boolean insert(String word) {
			boolean flag = true;
			TrieNode node = this.root;
			for (int i = 0; i < word.length(); i++) {
				node = node.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
				if (node.isLast())
					flag = false;
			}
			node.setLast(true);
			return flag;
		}

	}

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

		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; ++tc) {
			Trie trie = new Trie();
			N = stoi(in.readLine());
			boolean flag = true;
			List<String> list = new ArrayList<>();

			for (int i = 0; i < N; ++i)
				list.add(in.readLine());
			Collections.sort(list);

			for (String s : list)
				if (!trie.insert(s))
					flag = false;

			if (flag)
				sb.append("YES");
			else
				sb.append("NO");
			sb.append("\n");
		}
		System.out.println(sb);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}