설명

프로그래머스의 전화번호 목록 문제다.

여러 개의 전화번호 목록이 주어질 때 한 전화번호가 다른 전화번호의 접두사인지 확인하는 문제다. 접두사라는 문제의 조건 때문에 죄다 자료구조에 집어넣고 하나 하나 startsWith 메서드로 비교하면 될 것 같지만 효율성 테스트에서 실패하기 때문에 문제의 분류처럼 해싱을 사용하면 좀 더 빠르게 풀 수 있다.

풀이

처음에 시도했던 풀이는 일단 좀 더 효율적인 비교를 위해 전화번호 목록을 정렬하고 마치 선택 정렬처럼 한 요소와 나머지 요소를 전부 비교하는 방식이다.

    ...    
    int size = phones.size();
    for(int index = 0; index < size; index++) {
        for(int compare = index+1; compare < size; compare++) {
            if(phones.get(compare).startsWith(phones.get(index))) {
                return false;
            }
        }
    }
                
    return true;
    ...

리스트 자료구조에 삽입한 후 인덱스 기반으로 참조하며 String 클래스에 정의된 startsWith 메서드를 활용했으나 시간 초과가 발생했다.

그래서 생각한 다른 풀이는 어차피 비교할거라면 문자열을 자료구조에 삽입하는 시점에 비교하고 자료구조는 HashSet을 이용하여 해싱을 이용한 빠른 성능을 활용하자는 것이었다.

삽입하는 시점에 문자열을 처음 글자부터 마지막 문자까지 한 글자씩 늘려가며 자른 부분 문자열이 Set에 들어있는지 확인한다면 정렬된 문자열 특성상 유사한 문자열을 가진 전화번호들이 묶이리라는 생각에서 고안한 풀이다.

이를 기반으로 작성한 코드는 다음과 같다.

import java.util.*;


class Solution {
    public boolean solution(String[] phone_book) {
        // Arrays 클래스의 정렬 메서드로 문자열 정렬.
        Arrays.sort(phone_book);
        
        // Set 자료구조 활용.
        Set<String> phones = new HashSet<>();
        // 각 문자열을 자료구조에 삽입할 때 부분 문자열을 검사.
        for(String phone: phone_book) {
            if(phones.size() == 0){
                phones.add(phone);
                continue;
            }
            
            // 부분 문자열 생성, 검사.
            for(int part = 0; part < phone.length(); part++) {
                if(phones.contains(phone.substring(0, part))) return false;
            }
            
            // 접두사가 없는 전화번호라면 Set에 삽입.
            phones.add(phone);
        }
        
        return true;
    }
}

시간초과 없이 풀 수 있었다.

후기

문자열을 자르고 비교하는 과정에서 시간이 오래걸리지 않을까 걱정했는데 부분 문자열 자체는 그렇게 큰 영향이 없는 것 같다. 오히려 전화번호의 갯수가 매우 많아질 수 있기 때문에 해싱을 사용한 HashSet의 활용이 더 중요했던 것 같다.