[프로그래머스] #lv.2 - 전화번호 목록 (Java)

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

프로그래머스

# 힌트

입력 크기가 100만이라 2중 반복문을 통해서 하나하나 비교하면 효율성 테스트에서 걸리게 된다.

모든 요소를 전부 비교할 필요가 없다. phone_book 배열을 사전순으로 정렬하면, 인접한 요소끼리만 비교하는 것으로 충분하다.

왜냐하면 인접한 요소를 비교했는데 접두사가 아니면, 사전순으로 정렬된 후의 요소들도 당연히 아니기 때문이다.

 

 

해답 보기

public static boolean solution(String[] phone_book) {
    Arrays.sort(phone_book);
    String cur;
    String right = "";
    for (int i = 0; i < phone_book.length - 1; i++) {
        cur = phone_book[i];
        right = phone_book[i + 1];
        if (right.startsWith(cur)) return false;
    }
    return true;
}