전화번호 목록 - 자바

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

풀이

이번 문제의 포인트는 접두어이다. 여러 문자열들이 있는데 그 문자열들 중에 접두어가 있는지 없는지 확인하는 문제이기 때문에 단순하게 생각하면 중첩for문을 사용해 문자열을 일일이 확인하면 된다. 하지만 문자열 개수는 100만개이기 때문에 시간제한이 있다. 따라서 해쉬맵을 이용해야 한다. 접두어 문제이기 때문에 첫글자부터 끝글자 앞까지의 글자(전체 문자열을 저장하면 안된다. 이유는 마지막에 해당 문자열이 접두어인지 확인하기 위해서) 를 해쉬맵에 저장하고("123"이면 "1","12"를 저장) 모든 문자열이 저장되면 이제 접두어 확인하면 된다.

알게된 사실

str.substring(시작,끝);
str.substring(시작); //시작부터 문자열 끝까지

코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Map<String,Integer> map = new HashMap<>();
        for(int i=0;i<phone_book.length;i++){
            for(int j=0;j<phone_book[i].length();j++){
                map.put(phone_book[i].substring(0,j),1);
            }
        }
        for(int i=0;i<phone_book.length;i++){
            if(map.containsKey(phone_book[i])){
                answer=false;
                break;
            }
        }
        return answer;
    }
}