[Programmers] 전화번호 목록

[Programmers] 전화번호 목록

 

🎈문제

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 

💬설명

• 전화번호 목록이 있을 때 임의의 전화번호가 다른 전화번호의 접두어인 경우가 있는지 체크하는 문제
• 이중 for문을 이용해 풀어 줄 수도 있지만 "phone_book의 길이는 1 이상 1,000,000 이하입니다." 로 봐서 그렇게 하면 바로 효율성에서 틀릴 것 같았다.
• 따라서 모든 전화번호를 파이썬의 dictionary에 넣어두고(N) 전화번호 하나씩 돌아가면서(N) 처음-i번째까지가 dictionary에 있는지 체크(최대 20)하는 방식으로 풀어줬다. 이렇게 하면 dictionary는 찾는게 O(1)밖에 안걸리기 때문에 N정도 밖에 걸리지 않는다.

👩‍💻코드

def solution(phone_book):
    hash_map = {}
    # 모든 전화번호 딕셔너리에 넣기
    for number in phone_book:
        hash_map[number] = 0
    # 모든 전화번호 돌면서 접두어 있는지 확인
    for number in phone_book:
        number_len = len(number)
        for i in range(1, number_len):
            if number[:i] in hash_map:
                return False
    return True