[Programmers/JAVA] 05. 전화번호 목록

※  전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

 

문제 분석

전화번호의 배열 phone_book 이 주어질 때, 한 번호가 다른 번호의 접두어인지 구하는 문제이다.

어떤 번호가 다른 번호의 접두사인 경우가 있으면 fasle, 없으면 true 를 반환한다.

 

접근 방법

 정렬  을 사용하여 어떤 번호가 다른 번호의 접두사인지 살펴볼 것이다.

어떤 번호가 다른 번호의 접두사일 경우, 정렬된 배열 phone_book 에서 두 번호는 반드시 붙어있게 된다.

따라서 배열을 정렬한 후, $i$ 번째 번호가 $i + 1$ 번째 번호의 접두사인지 확인하면 된다.

 

배열의 길이를 $N$, 전화번호의 길이를 $M$ 이라고 할 때, 정렬에 $O(NlongN)$, 탐색에 $O(MN)$이 소요된다.

따라서 평균 시간 복잡도는 $O(NlogN) + O(MN) = O(NlogN)$이다.

$N$의 최대값은 $10^{6}$이므로 시간 초과가 발생하지 않는다.

 

코드 설계

# 배열 phone_book 를 정렬한다.

# phone_book[i] 값이 phone_book[i-1] 값으로 시작한다면 false를 반환하고, 아니면 true를 반환한다.

# 단, 루프 변수가 0부터 시작하면 이전 값이 존재하지 않으므로 루프 변수는 1부터 시작하여야 한다.

 

코드 구현

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i=1; i<phone_book.length; i++) {
            if(phone_book[i].startsWith(phone_book[i-1])) {
                return false;
            }
        }
             
        return true;
    }
}

 

---

 

접근 방법

 해시 테이블  을 사용하여 어떤 번호가 다른 번호의 접두사인지 살펴볼 것이다.

전화번호의 배열 phone_book 의 원소를 해시테이블에 추가한다.

phone_book 원소에서 부분 문자열을 생성하여 해시테이블에 일치하는 값이 있는지 확인한다.

 

코드 설계

# 해시테이블을 선언하고  phone_book 의 원소를 추가한다.

# phone_book 원소를 돌며 부분 문자열을 생성한다.

# 부분 문자열 중 해시 테이블의 값과 일치하는 값이 존재하면 false 를 반환하고 없다면 true 를 반환한다.

 

코드 구현

import java.util.*;

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