1 ★★★ [프로그래머스][JAVA] 전화번호 목록 (문자열)

220607

효율성 3,4 실패

(수정전)으로 돌릴 시 시간복잡도 n^2

(수정후)으로 돌릴 시 시간복잡도 nlogn

 

 

 

 

효율성 3,4번 실패함

O(n^2)으로 풀어서 그런듯

O(n)으로 해결이 되는데 정렬 후에(사전 순으로)

앞뒤 문자만 체크해줘도 해결이 되는 방식이 뭔가 신기했다..

 

 

(수정 전)

import java.util.*;
 
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
 
        for(int i=0; i<phone_book.length; i++){
            for(int j=i+1; j<phone_book.length; j++){
 
                if(phone_book[j].startsWith(phone_book[i])) return false;
                if(phone_book[i].startsWith(phone_book[j])) return false;    
 
            }
 
            System.out.println(phone_book[i]);
        }
 
        return answer;
    }
}

 

 

(수정 후)

import java.util.*;
 
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        // for(int i=0; i<phone_book.length; i++){
        //     System.out.println(phone_book[i]);   
        // }
        
        for(int i=0; i<phone_book.length-1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])) return false;
                  
        }
        return true;
    }
}