문제

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

나의 코드 (답안참조)

"""
1. 아이디어
해시를 활용한 풀이

2. 시간복잡도

"""

def solution(phone_book):
    
    # 1. hashmap을 만든다.
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
        
    # 2. 접두어가 해시에 존재하는지 확인한다.    
    for phone_number in phone_book:
        jubdoo = ""
        
        for number in phone_number:
            jubdoo += number
            
            # 3. 접두어를 찾는다. (기존 번호와 같은 경우 제외)
            if jubdoo in hash_map and jubdoo != phone_number:
                return False
    
    return True
    

생각해봐야 할 것

다음과 같이 hash_map 즉 딕셔너리를 따로 만들지 않고 넘겨받은 phone_book 리스트 자료형 그대로 in 연산을 했는데 시간초과가 나왔다. 그 이유는 in 연산자는 다음과 같은 시간 복잡도를 가지기 때문이다.

• list, tuple
  
  Average: O(n)
  하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.
  
  
• set, dictionary
  Average: O(1), Worst: O(n)
  내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

결론은 해시(hash)를 사용해야 하는 이유를 말해줄 수 있다.

느낀점

hash_map은 접두어를 모아놓은 곳이고

if jubdoo in hash_map and jubdoo != phone_number:
이 부분에서 결국 hash_map(접두어 모음)과의 비교를 통해 찾아낸다.
또한 자기 자신인 경우를 제외 하기 위해 and 뒤의 연산을 해준 것이다.