[알고리즘] 전화번호 목록

문제

문제 링크

풀이

예를 들어 phone_book 배열이 ["12","123","1235","567","88"] 처럼 주어졌을 때 1235에 12가 포함되므로 접두사가 되며 false가 정답이 된다. 이를 단순하게 확인하려면 모든 원소에 대하여 모든 다른 원소와 비교하면 문제는 해결되지만 시간복잡도가 O(n^2)이 되어 효율성 테스트에서 오답이 나오게 된다.

O(n)에 문제를 해결하려면 한번만 순회하면서 답을 찾아야 한다. 이를 위해서는 각각의 자릿수에 대하여 더 작은 수가 앞에 오도록 정렬을 해주면 된다. 예를 들어 "12"와 "123" 이 있다면 "12", "123"으로 정렬을 해야 하고 "1"과 "123" 이 있다면 "1", "123"으로, "2"와 "24"와 "134"이 있다면 "134", "2", "24"로 정렬을 수행해야 한다. 이렇게 하면, 바로 직전의 수가 다음 수에 포함되는지 확인하는 것만으로 전체 수간에 접두사 관계가 존재하는지를 확인할 수 있게 된다.

맨 앞에 "1" 이 있고 한참 뒤에 있는 "123"의 경우 맨 앞의 "1"이 접두사로 인식되지 못하는 것 아닌가? 하는 생각이 들었지만 생각해보면 "1"과 "123" 사이에 아무런 숫자가 없다면 붙어있으므로 당연히 접두사로 인식될 것이고, 사이에 숫자가 있다면 무조건 "1"을 포함하는 숫자일 것이므로 이러한 문제는 발생하지 않는다.

자바에서 문자열로 이루어진 배열을 정렬하면 앞서 말한 것처럼 정렬을 수행해준다. 따라서 정렬을 수행한 후 String 클래스의 startsWith() 메서드를 통해 현재 문자열이 직전의 문자열로 시작되는지를 확인하면 된다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // "1", "1xx", "1xxx", "2", "24", "59", "599", ...
        Arrays.sort(phone_book);       

        for (int i = 1 ; i < phone_book.length ; i++) {
            // 현재 문자열이 직전 문자열로 시작하는지 확인
            if (phone_book[i].startsWith(phone_book[i - 1])) {
                return false;
            }
        }
        // 접두사 관계가 없다면 true 반환
        return true;
    }
}