[Algo] 백준 5052 전화번호 목록 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/5052

메모리 : 32052KB

시간 : 540 ms

언어 : Java 8

---

코드

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

public class Main {
	// 트라이 알고리즘을 써보자!
	static class Node {
		Map<Character, Node> chiledNode = new HashMap<>();
		// boolean isleaf; 사실 이문제에서는 필요없음
	}

	static class Trie {
		// 루트노드 생성
		Node rootNode = new Node();

		void insert(String str) {
			// 루트노드부터 시작하게
			Node node = this.rootNode;
			for (int i = 0; i < str.length(); i++) {
				// computeIfAbsent : 없으면 넣어주고, 있으면 값 리턴
				// chiledNode에 해당 글자가 없으면 그 글자 넣기
				node = node.chiledNode.computeIfAbsent(str.charAt(i), key -> new Node());
			}
			// 한바퀴 다 돌았으면 맨 마지막 노드에 true를 넣어준다.
			// node.isleaf = true;
		}

		boolean search(String str) {
			Node node = this.rootNode;
			for (int i = 0; i < str.length(); i++) {
				// getOrDefault : 값 리턴하거나 값이없으면 디폴트값 리턴
				// get 해도 됨
				node = node.chiledNode.getOrDefault(str.charAt(i), null);
				if (node == null) {
					// 해당 문자열은 일치하지 않는다.
					return false;
				}
			}
			// return node.isleaf; //일치했다면 맨 끝에 isleaf가 true 겠지 근데 이문제에선 노필요
			return true; // 일치하면 true 반환
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			Trie trie = new Trie(); // 매번 새거만들어서 충돌방지
			boolean flag = true;
			int N = Integer.parseInt(br.readLine());
			String[] arr = new String[N];
			for (int i = 0; i < N; i++) {
				arr[i] = br.readLine();
			}
			/*
			 * 정렬하면 길이순으로 정렬된다.
			 * 문제에서 같은 숫자가 들어가지않는다고 했기 때문에 같은 길이에서는 서로 비교할 필요가 없음
			 * 긴 길이부터 시작해 짧은 길이로 탐색해야한다.
			 */
			Arrays.sort(arr);
			// 제일 긴거 넣고
			trie.insert(arr[N - 1]);
			for (int n = N - 2; n >= 0; n--) {
				// 그 다음거랑 비교탐색 후
				if (trie.search(arr[n])) {
					// 일치하면 일관성 없다..
					flag = false;
					break;
				}
				// 해당 문자열 넣기
				trie.insert(arr[n]);
			}
			if (flag) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}