문제링크

풀이1

첫번째 풀이는 해시를 사용한 완전 탐색 풀이다.
HashSet을 선언 후 전화번호부에 있는 모든 번호를 set에 저장한다.
현재 전화번호의 길이를 1 ~ 전화번호길이 까지 substring으로 자르며 잘려진 전화번호를 map이 key로 가지고 있는지 탐색한다. 가지고 있다면, 접두어가 존재하는 것이므로 false를 리턴한다.

코드1

import java.io.*;
import java.util.*;
 
 class Solution {
     public boolean solution(String[] phone_book) {
         boolean answer = true;
         
         Map<String, Integer> map = new HashMap<>();
         for(String str : phone_book) { 
             map.put(str, 0);
         }
         
         for(int i = 0; i<phone_book.length; i++) {
             for(int j = 1;j<phone_book[i].length(); j ++) {
                 if(map.containsKey(phone_book[i].substring(0,j))){
                     answer = false; 
                     return answer;
                 }
             }
         }
         
         return answer;
     }
 }

풀이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 - 1; i++) {
            String current = phone_book[i];
            String next = phone_book[i + 1];
            
            if (next.startsWith(current)) {
                return false;
            }
        }

        return true;
    }
}