[코딩테스트 - Java] 프로그래머스 전화번호 목록

프로그래머스 LEVEL 2 - 해시 - 전화번호 목록

전화번호부 목록에서, 한 번호가 다른 번호의 접두사가 되는지를 판별하는 문제.
처음 2중 for 문으로 풀었고 효율성 3, 4번에서 시간초과가 났다.

알고리즘: 사전 순으로 정렬 후 바로 뒤 인덱스와 비교하기

사전 순으로 정렬하게 되면 앞쪽이 비슷한 번호들끼리 정렬되게 된다.

12 567 88 123 1235 를 사전순 정렬 시
12 123 1235 567 88 가 되므로, 붙어있는 인덱스 끼리 비교하면 됨

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        // 사전 순 정렬
        Arrays.sort(phone_book);
        
        for(String data : phone_book){
            System.out.print(data+" ");
        }
        // 사전 순 정렬 후에는 바로 뒤 인덱스만 탐색해도 됨
        for(int i=0;i<phone_book.length-1;i++){
            if(phone_book[i+1].startsWith(phone_book[i])){
                return false;
            }
        }
        return true;
    }
}