[프로그래머스,자바] Level2: 전화번호 목록 (2021년 업데이트)

 

문제분석

 

작년에 쉽게 풀었던 문제가  2021년 3월 4일 업데이트 되었습니다.

 

문제는 정말 간단합니다.

전화번호가  다른전화번호의 접두어가 되면 false, 아니면 True입니다.

 

이제보니, 작년에 그냥 해시를 안쓰고 2중반복문을 써서 풀었더라구요.

 

이번에 업데이트된 테스트케이스로 다시 실행해보니, 효율성이 막힙니다.

하긴.. 해시를 안쓰고 해시문제라고 못하지

 

일단, 무조건 n^2 을 시도하시면 통과못합니다.

 

그러면, 어떻게든 줄여봐야죠. 해시를 쓰라고했으니, 해시를 사용해봅시다.

 

Hash를 갖고있는 자료구조가, HashSet, HashMap이 대표적인데,  둘 중 아무거나 써도 됩니다.

실제로 연산속도가 둘이 비슷하더라고요.

 

필자는 HashSet,HashMap 둘다 사용해봤습니다.

 

우선, 풀이법부터 공유하겠습니다.

 

1. HashSet 또는 HashMap에 모든 전화번호부를 넣는다. (1중for문)

 

2. 모든 전화번호부를 돌면서, 전화번호부를 1글자~본인의 전화번호부길이만큼 자릅니다.(1중for)

 

3.Set에 저장된 Key와 자른 전화번호부가 포함되어있는지(contains()메소드)  확인합니다.(2중for)

 

 

->잠깐, 2중반복문 쓰면안된다면서요?!

 

3번에 시행된 2중for문은 최대 20번만돕니다. <전화번호부의 길이는 20으로 제한>

즉, 형태는 2중for문이지만 어떻게보면 최대 20*O(n) 이죠.

 

-> 아니..  contains()메소드 때문에 O(n)이 시간이 더 드는거 아닌가요? 자른 전화번호부를 모든 Set원소에 비교하는건데

 

No! contains()메소드는 O(1)인 상수시간입니다. 이것이 바로 해시의 강력함이죠.

이게 가능한 이유가, Hash로 지정한 Key값을 하나의 idx로 보고, idx를 바로 찾아주는거에요.

contains(key)같은경우는, key를 포함하는지 안하는지 단 1번의연산으로 찾아주죠.   

 

예시로들면, 과일가게 아저씨한테  사과 있어요?  물어보면 사과 있거나 없다고 바로 나오잖아요.

 

사과 있냐고 물어봤는데 과일가게 아저씨가 복숭아, 수박, 포도, 바나나, 하나씩 찾아보다가 사과를 찾지는 않죠?

 

 

이렇게 계산하면, 최대 O(n)+ 20*O(n)입니다.

 

2중반복문보다 많이 줄엇네요.

 

문제풀이

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Set set = new HashSet<>();
        for(int i = 0 ; i < phone_book.length ; i++){
            set.add(phone_book[i]);
        }
        for(int i = 0 ; i < phone_book.length ; i++){
            int size=phone_book[i].length();        
            for(int j = 1 ; j <size; j++ ){
                if(set.contains(phone_book[i].substring(0,j)))  return false;    
            }              
        }
                    
        return answer;
        
    }
}