프로그래머스 : 전화번호 목록 Java

코딩테스트 연습 - 전화번호 목록
이 문제는 길이에 따라 정렬한 뒤, 그 길이보다 짧은 번호들을 모두 확인해보는 것이 핵심이다.
나는 Set<Integer>[]을 사용했는데, Set의 contains를 사용할 경우 O(1)의 시간으로 찾을 수 있기 때문이다. 따라서, 길이를 len이라고 뒀을 때, O(len)의 시간으로 해당 전화번호의 접두사가 있는지 확인할 수 있다.

정렬을 하는 이유는 길이가 긴 번호가 앞에 올 수 있는데, 이 때는 나중에 짧은 번호가 들어왔을 때 다른 번호의 접두사인지 확인할 수 없기 때문이다. 따라서, 반드시 정렬을 먼저해 접두사로 사용될 번호들을 저장해두고 확인해야 한다.

해당 전화번호에 접두사가 있는지 확인하는 로직은 아래와 같다.

for(String number : phone_book){
    int len = number.length();
    for(int i = 1; i < len; i++){
        if(prefix[i].contains(number.substring(0, i))){
            return false;
        }
    }
    prefix[len].add(number);
}

정렬된 전화번호부에서 하나를 꺼낸 후, (길이 - 1)까지 접두사 배열을 확인한다.
여기서 numbers.substring(0, i)는 앞서 저장해둔 짧은 번호들과 짧은 번호들의 길이만큼 현재 번호에서 떼고 그 둘이 일치하는지 확인하는 작업이다.
예제와 같이 119와 1195524421가 있을 때, 1195524421을 앞에서 3글자만 떼어 Set에 있는지 확인하게된다. 이 경우에는 119가 1195524421에서 3자리 뗀 119와 일치하므로 바로 false를 반환한다. 모든 번호를 확인해봐도 접두사가 없을 경우 true를 반환한면 된다.

전체코드

import java.util.*;

class Solution {
    static Set<String>[] prefix = new Set[21];
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for(int i = 0; i < 21; i++){
            prefix[i] = new HashSet<>();
        }
           for(String number : phone_book){
            int len = number.length();
            for(int i = 1; i < len; i++){
                if(prefix[i].contains(number.substring(0, i))){
                    return false;
                }
            }
            prefix[len].add(number);
        } 
        return true;
    }
}