🔔 답안만 쏙쏙 골라보고싶으신 분들께
풀이 과정과 접근 방법 없이, 문제에 대한 해설만 보고싶으시다면 접근2. 해시 | ContainsKey 로 가주시기 바랍니다.

전화번호 목록

📄 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

🚫 제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

접근1. 이중for문 | startsWith

👁‍🗨 접근방식

String.startsWith() 메서드를 통해, 입력받은 모든 배열의 요소들을 다른 요소에 대한 접두어인지 확인한다.
이중for문을 통해, 배열 내에서 2개의 요소를 뽑는 모든 경우의수를 구한 뒤, 각 경우의수별로 startsWith 을 통해 검사한다.

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

⛔ 발생한 문제

제출 후 채점하기시, 효율성테스트 3번, 4번을 통과하지 못한다
원인 탐색

• 이중for문으로 인해 시간복잡도가 O(Tri n) 이 된다.

다음 추론을 바탕으로, 이중for 문을 사용하지 않는 새로운 로직을 고민하던중, HashMap 의 containsKey 의 시간복잡도가 O(1) 이라는 점을 통해 이중for문을 사용하더라도 최적화가 가능한 로직을 떠올리게 되었다

접근2. 해시 | ContainsKey

👁‍🗨 접근방식

입력받은 배열 내의 모든 요소들을 HashMap 에 put 한다.
이후, 입력받은 배열 내의 요소들을 iteration 한다. 이때 각 요소들을 el 이라 한다.
el을 이터레이션하여 마지막 인덱스부터 자른다 (예상되는 접두어를 구하기 위함)
이후, map.containsKey 를 통해 특정 요소가 el 의 접두어인지 확인한다

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean solution(String[] phone_book) {
        Map<String, Void> map = new HashMap<>();
        for (String phone : phone_book) {
            map.put(phone, null);
        }
        for (String phone : phone_book) {
            for(int i = 1; i < phone.length(); i++) {
                String sub = phone.substring(0, i);
                if(map.containsKey(sub)) return false;
            }
        }
        return true;
    }
}

결과

정확성 테스트 및 효율성 테스트를 전체 통과하였다