전화번호 목록

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++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                answer = false;
                break;
            }
        }
        return answer;
    }
}

처음엔 HashSet 이중 for문으로 수행했지만 효율성에서 걸리게 되었다.

그래서 효율성을 생각하다가 문자열 정렬이 떠올랐다.

phone_book = { "119", "97674223", "1195524421" }
Arrays.sort(phone_book);
 
결과 : 119 1195524421 97674223

문자열이 다음과 같을 때 정렬을 하게 되면 문자열은 사전식으로 정렬되게 된다.

글자 수가 작은 순, 글자가 똑같은 순으로 정렬되기 때문에 바로 뒤에 있는 문자만 확인하면 된다.

그리고 접두사를 기준으로 판단하기 때문에 contains가 아닌 startWith로 시작 문자열을 검사해야 한다.