[알고리즘 TIL] 전화번호 목록(Java, 해시)

문제

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

프로그래머스

프로그래머스 LV2

설명

전화번호부에 들어있는 전화번호의 수는 최대 1,000,000개이다. 따라서 만약 모든 전화번호와 대조한다면 1,000,000*1,000,000 의 최악의 시간이 걸리게 된다.

 

그렇다면 어떻게 시간복잡도를 효율적으로 구현할 수 있을까? 전화번호는 자릿수가 20이라는 제한이 있다. 따라서 각 전화번호마다 자릿수만큼 subString을 구해서 해당 subString이 다른 전화번호랑 일치하는지 확인한다. 이때, substring이 O(n), containsKey가 O(1) 이므로 O(400*N)으로 해결할 수 있다.

 

따라서 이 문제에서는 조회 성능이 뛰어난 해시(HashMap) 자료구조를 사용하는 것이 매우 적합하다.

구현

import java.util.*;

class Solution {
   public boolean solution(String[] phoneBook) {
            boolean answer = true;

            HashMap<String, Integer> hashMap = new HashMap<>();
            int index = 0;

            for(String phoneNumber : phoneBook) {
                hashMap.put(phoneNumber,index++);
            }

            for(String phoneNumber : phoneBook) {
                for(int i=0;i<phoneNumber.length();i++){
                    String prefix = phoneNumber.substring(0, i);
                    if(hashMap.containsKey(prefix)) {
                        answer = false;
                        break;
                    }
                }
            }

            return answer;
        }
}