[JAVA] 해시 : 전화번호 목록

문제내용

처음 문제를 풀었을 때 정렬을 하면 쉽지않나?라는 생각으로 문제를 풀어봤다

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
    	// 정렬
        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;
    }
}

위의 코드로도 해결이 되지만 해시로도 해결해보고 싶었다


해시로 구현한다면 이렇게 구현할 수가 있다

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> phoneSet = new HashSet<>();

        // 모든 전화번호를 해시에 저장
        for (String phone : phone_book) {
            phoneSet.add(phone);
        }

        // 모든 번호를 한글자씩 늘려가며 비교
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);
                if (phoneSet.contains(prefix)) {
                    return false;
                }
            }
        }

        return true;
    }
}

일단 둘의 시간복잡도는 정렬은 NlogN 해시는 평균적으로 N*L이지만 최악의 경우 N*(L^2)까지도 나올 수 있다
하지만 평군적으로 해시가 빠르다고 볼 수 있으므로 해시를 사용하는게 더 좋은 경우가 많다라고 생각할 수 있다