문제 출처

코딩테스트 연습 > 해시 > 전화번호 목록
https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제 설명

전화번호 배열이 주어질 때, 한 번호가 다른 번호의 접두어인 경우가 있을 때 return false, 없을 때는 return true 한다.

접근 방법

HashMap에 key는 전화번호를 삽입하고, value는 1로 지정한다.
2중 for문을 이용해 바깥 쪽 for문은 배열의 요소를 지정, 안쪽 for문에서 해당 배열 요소의 substring을 (0,i) 만큼 추출하여 HashMap에 key로 등록되어있는지 확인하여 있으면 false를 return 한다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String phone : phone_book) {
            map.put(phone, 1);
        }

        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);

                if (map.containsKey(prefix)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

알게된 점

처음에 혼자 풀었을 때는 java의 접두사를 확인 할 수 있는 기능인 startsWith 메서드를 이용하여 풀었다. 하지만 이는 전화번호를 한 번 순회하는 시간이 추가되어 시간 복잡도가 늘어난다. 내가 풀이한 방법은 O(n^2 x K) (K는 문자열의 길이)가 되어 시간복잡도가 꽤나 길었다.
문제의 정답으로 배열의 요소를 substring으로 추출하여 containsKey 메서드를 이용하면 containsKey의 시간 복잡도는 O(1) (해시를 활용하기 때문) 이므로 최종 시간 복잡도는 O(n x k^)로 짧아진다.

처음 푼 풀이

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        String str;
        
        HashMap<Integer, String> hm = new HashMap<>();
        Arrays.sort(phone_book);
        for(int i = 0; i<phone_book.length; i++){
            hm.put(i,phone_book[i]);
        }
        for(int i =0; i<phone_book.length; i++){
            str = hm.get(i);
            for(int key: hm.keySet()){
                if(i==key){
                    continue;
                }
                else if(str.startsWith(hm.get(key))==true){
                    return false;
                    }
                }
            }
        return true;
        }
    }

문제푼 흔적