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

전화번호를 정렬하면 $i$번째 전화번호가 $i+1$번째 전화번호의 접두어가 되는지만 검사하면 되기 때문에 시간 복잡도가 $O(N^2)$에서 $O(log(N) \times N)$으로 감소한다.

Solution

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        List<String> l = new ArrayList(Arrays.asList(phoneBook));
        Collections.sort(l);
        if (l.size() == 1)
            return true;
        for (int i = 0; i < l.size() - 1; i++)
            if (l.get(i + 1).startsWith(l.get(i)))
                return false;
        return true;
    }
}

startsWith 메서드를 사용하여 $i$번째 문자열이 $i+1$번째 문자열의 접두어가 되는지를 효율적으로 검사할 수 있었다.