[프로그래머스] 전화번호 목록

출처 : 프로그래머스 전화번호 목록(Level 2)

해시를 이용하면 쉽게 풀린다.
우선, 모든 전화번호를 Hash map에 Key로 설정해두고

전화번호부의 번호들을 다시 순회하며
번호를 한글자씩 꺼낸다. ""에 하나씩 추가해가면서
해당 글자가 Key에 존재하면서 글자와 Key가 똑같지 않으면 False를 return 하고 끝까지 그런 값이 없으면 True를 Return한다.

시간복잡도는 X+X*Y로 X = 1~1,000,000, Y = 1 ~ 20으로 해결될 수 있다. 글자 수가 번호 갯수에 비해 상당히 낮으므로 글자 수를 하나씩 순회하는 방법이 상관없었는데 조금 더 효율적인 비교방법이 있을까? 궁금하다.

해쉬를 선언한 이유는 해당 글자가 Key에 존재하면서 에서 활용하기 위함인데 list에서 특정 문자열이 있는지 찾는 것은 $O(n)$ 시간복잡도로 최종적으로 시간복잡도가 $O(n^2)$이 된다.

그러나 Hash map을 통해 Key를 찾는것은 $O(1)$이 되므로
시간복잡도를 만족할 수 있다.