21. Programmers Level 2. '전화번호 목록'

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

프로그래머스

 

원래 for문으로 완전탐색으로 진행했지만 시간초과가 났다. 따라서 해시로 다시 접근했던 문제

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

containskey를 이용해 차례로 문자열을 앞에서부터 잘라서 해시값과 일치하는 값이 있는지 확인하는 과정을 거쳤다.

얼핏 보기에는 하나씩 검사해야 하기에 시간이 오래 걸릴 것 같지만, 해시의 시간복잡도가 워낙 작아서 통과 가능한 것 같다!