1. 문제 설명 📌

문제 링크

문제에서 원하는 것은 A의 전화번호를 치고 있던 와중에, B의 전화번호를 완성시켜서, B로 전화가 걸리는 일이 없으면 일관성이 TRUE, 전화가 한 번이라도 걸리면 FALSE라는 뜻이다.

즉 '하나의 전화번호가 다른 전화번호의 접두어가 되는지?'를 확인하라는 문제이다.

2. 구현 방법 🗃️

KEY WORD: TRI

기본적인 트라이를 그대로 사용한 문제라 따로 부연 설명할 것이 없다. 아직 트라이에 대한 개념이 없다면, 미리 학습 하고 오시길 바란다.

0️⃣ HashMap을 활용하여 전형적인 트라이 구조 트리를 구현한다. + 문자열을 삽입하는 insert 매소드를 구현한다.
1️⃣ 문자열 (이하 str)을 트라이에 삽입한다.
2️⃣ 만약 str을 삽입하는 도중에, 현재 조회 중인 문자가 어떤 문자의 끝임을 알리는 isEnd가 TRUE이면, 거기서 삽입을 멈추고 나온다. 왜냐하면, 이미 str의 접두어가 존재한다는 의미이미로, 현 전화번호 목록은 일관성이 없다.
3️⃣ str 삽입이 끝났는데, 마지막 문자의 자식이 트라이 내부에 존재한다. 현재 넣고 있는 str 자체가 어떤 문자의 접두어가 된다는 의미 이므로, 전화번호 목록의 일관성이 없다.
4️⃣ 2번이나 3번에 해당 한다면 "NO" 출력, 둘을 무사히 빠져나오면 "YES" 출력

(1) 시간복잡도 분석 🕓

테스트 케이스의 개수 T, 전화번호부의 개수 N, 문자열의 길이 L

문자열 하나를 트라이에 삽입하는 시간 복잡도: $O(L)$
최악의 경우, 모든 테스트 케이스 내의 모든 전화번호부를 모두 트라이에 넣어야 함. : $O(T * N * L)$

테스트 케이스 개수(최대 50개) x 각 테스트 별 전화 번호 개수 (최대 10000개) x (각 전화번호의 최대 길이 10개) = 총 50만번의 연산이 필요함.

따라서 시간 내에 풀 수 있음.

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int T, N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder ans = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            Tri tri = new Tri();
            boolean isValid = true;
            for (int i = 0; i < N; i++) {
                String now = br.readLine();
                if(!tri.insert(now)) isValid = false;
            }
            ans.append(isValid? "YES" : "NO").append("\n");
        }
        System.out.println(ans);
    }
}

class Tri {
    Node root;

    public Tri () {
        root = new Node();
    }

    public boolean insert(String str) {
        Node cur = this.root;   // 초기화
        for (int i = 0; i < str.length(); i++) {
            char now = str.charAt(i);
            cur.child.putIfAbsent(now, new Node());
            cur = cur.child.get(now);
            if(cur.isEnd) return false; // 현재 값을 넣고 있는 도중인데, isEnd = true 되어 있으면 이 문자열은 접두사가 존재한다는 뜻
        }
        cur.isEnd = true;
        if(!cur.child.isEmpty()) return false; // 현재 값을 다 넣었는데, 하위노드가 존재, 이 문자열은 어떤 문자열의 접두사이다.
        return true;
    }

}

class Node {
    HashMap<Character, Node> child;
    boolean isEnd;

    public Node(){
        child = new HashMap<>();
        this.isEnd = false;
    }
}