시도 1. String.indexOf() 함수를 이용한 비교

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        for(String x : phone_book){
            for (String y : phone_book){
                if(x.indexOf(y) == 0 && x != y){
                    return false;
                }
            }
        }
        return true;
    }
}

→ 효율성 테스트에서 $O^2$로 시간 초과

시도 2. 정렬하여 반복 회수를 줄인 비교

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i =0;i<phone_book.length;i++){
            for(int j=i + 1;j<phone_book.length;j++){
                if(phone_book[i].startsWith(phone_book[j]))
                    return false;
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        return true;
    }
}

→ 효율성 테스트에서 $N^2$로 시간 초과

시도 3. HashSet 이용

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> hs = new HashSet<>();
        for(String x: phone_book){
            hs.add(x);
        }
        for(String x: phone_book){
            for(int i =0;i<x.length();i++){
                if(hs.contains(x.substring(0,i))){
                    return false;
                }
            }
        }
        return true;
    }
}

→ 얼핏 보기에는 for 반복문이 중첩되어 보여 $N^2$ 라고 생각할 수 있지만, 문제에서 "각 전화번호의 길이는 1이상 20이하"라고 충분히 작은 수를 조건으로 주었기에 $20N$ → $N$ 이라고 할 수 있다.