해시 - 전화번호부

문제

• 전화번호 목록에서 어떤 번호가 다른 번호의 접두어인지 확인하는 문제.
• 접두어 관계가 하나라도 있으면 false
• 접두어 관계가 없으면 true
• 예를 들어 119와 1195524421이 있으면, 119가 1195524421의 접두어이므로 false.

조건

• phone_book 길이: 1 이상 1,000,000 이하
• 각 전화번호 길이: 1 이상 20 이하
• 같은 전화번호는 중복되지 않음

핵심

• 전체 쌍 비교 O(N^2)는 불가능
• 정렬 후 인접 비교 O(N log N)으로 해결 가능

import java.util.*;
 
class Solution {
    public boolean solution(String[] phone_book) {
 
        /*
         * 실패 1: 전체 쌍 비교
         * O(N^2) → 최대 1,000,000개라 시간 초과.
         */
        
//        for (String origin : phone_book) {
//            for (String copy : phone_book) {
//                if (origin.equals(copy)) continue;
//                if (origin.startsWith(copy)) return false;
//            }
//        }
 
 
        /*
         * 실패 2: 정렬은 했지만, 다시 이중 반복문을 돌림
         * 정렬 후에도 모든 뒤쪽 번호를 비교하면 최악 O(N^2)에 가까워짐.
         */
 
//        Arrays.sort(phone_book);
//
//        for (int i = 0; i < phone_book.length - 1; i++) {
//            for (int j = i + 1; j < phone_book.length; j++) {
//                if (phone_book[j].startsWith(phone_book[i])) return false;
//            }
//        }
 
 
        /*
         * 가능 1: 정렬 후 바로 다음 번호만 비교
         * 문자열 정렬을 하면 접두어 관계가 있는 번호들은 서로 인접하게 모인다.
         *
         * 정렬: O(N log N)
         * 인접 비교: O(N)
         * 전체: O(N log N)
         */
        
        Arrays.sort(phone_book);
 
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }
 
        return true;
    }
}