Lv 2. 전화번호 목록

 

처음에는 비교할 문장이 2개 이니까 2중루프를 통해 구현하였고 바로 시간초과오류가 발생하였다.
다음은 Map 을 사용한 해싱을 이용하여 풀이한 코드이다.
주어진 문제에서 비교군을 대상으로 하면 1000000*1000000 이지만
전화번호의 길이를 대상으로 하면 1000000*20 이더라.
이를 이용하였다. containsKey라는 메서드를 이용하여 풀이하였다.
containsKey는 해싱을 이용한 함수로 시간복잡도가 O에 달하는 효율적인 탐색 메서드이다.
중복된 전화번호가 없기에 사용할 수 있었다.

import java.util.*;

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