전화번호목록

자바 문제 풀이

import java.util.*;

public class 전화번호목록 {
    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++){
               String s1 = phone_book[i];
               String s2 = phone_book[j];
                
               if(s1.length()<= s2.length())
               s2 = s2.substring(0,s1.length());
        
               if(s1.equals(s2)){
                    return false;
               }    
            }
        }
       return true;
   }
}

이중 for문을 반복하여 문자 두개를 비교하였다. 첫번째 문자열 길이 만큼 두번째 문자열을 잘라 같으면 바로 false를 리턴하도록 하였다.

테스트 케이스는 모두 통과했지만 효율성 테스트 2개를 통과하지 못했다.

검색 결과 이보다 더 간단한 방법이 있었다.! 바로 startsWith 메소드 이다.

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++){
             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;
    }
}

하지만 이 방법도 효율성 테스트를 통과하지 못했다.

Hash를 이용해서 풀었을 때는 효율성까지 통과할 수 있었다.

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