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

<문제>

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

프로그래머스

 

<풀이>

def solution(phone_book):
    phone_book_dict = {value: True for value in phone_book}
    
    for number in phone_book:
        for i in range(1, len(number)+1):
            prefix = number[0:i]
            if prefix in phone_book_dict and prefix != number:
                return False
    
    return True

 

- 2차 배열 순회로는 효율성에서 실패함 (백만 x 백만, n^2)

- 2차 배열이지만 요소의 length만큼만 돌면 되니까 문제 조건에 따라 백만 x 20 임

- 해시 조회도 사용 O(1)

- 해시의 값은 필요없음 (아무거나 해도 됨)

- 요소의 숫자를 하나씩 더해가면서 해시테이블의 키에 조회가 되는지 확인