[프로그래머스, JAVA] 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

- Test는 모두 통과했지만 효율성 테스트를 통과하지 못한 코드

중첩 for문이라 시간복잡도가 O(n^2)이 돼서 그런 것 같음

class Solution {
    public boolean solution(String[] phone_book) {
        //한 번호가 다른 번호의 접두어인 경우 확인
        //우선 정렬을 하고 비교 -> 길이순으로 정렬
        
        boolean answer = true;
        
        for(int i=0; i<phone_book.length - 1; i++){
            for(int j=i+1; j<phone_book.length; j++){
                if(phone_book[i].length() <= phone_book[j].length()){
                    if(phone_book[j].startsWith(phone_book[i])){
                        answer = false;
                    }
                } else {
                    if(phone_book[i].startsWith(phone_book[j])){
                        answer = false;
                    }
                }
            }
        }
        return answer;
    }
}

 

 

- 정답 코드

정렬을 한 후 그 앞부분과 비교하면 된다

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        //오름차순 정렬
        Arrays.sort(phone_book);
        for(int i=0; i<phone_book.length - 1; i++){
            String front = phone_book[i];
            String back = phone_book[i+1];
            if(back.startsWith(front)){
                answer = false;
            }
        }
        return answer;
    }
}