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

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

프로그래머스

문제

---

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하라.

 

입력

---

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

출력

---

true or false

 

풀이

---

그냥 기본 으로 탐색하게 된다면 phone_book 을 두번돌리게 된다. 따라서 1000000000000이라는 for문을 돌리게 되는데 매우비효율적이다.

 

일단 phone_num_dict 에 phone_book 의 리스트들을 딕셔너리로 넣어준다.

 

그리고 전화번호부에 있는 모든 전화번호에 길이 1부터 최대 해당 전화번호의 길이까지 phone_num_dict 에서 찾는다.

만약 있다면 False 를 리턴한다. 모두 없다면 True 를 리턴한다.

 

for 문은 1000000 * 20 로 빨라진다.

 

def solution(phone_book):
    answer = True 
    phone_num_dict = {i:0 for i in phone_book} # phone_book 에있는 모든 번호를 해시로 만든다.
    for phone_num in phone_book: # 모든 전화번호를 돈다.
        for i in range(len(phone_num)): # 1부터 전화번호의 길이 전까지 해시에 등록되어있는지 살핀다.
            if phone_num[:i] in phone_num_dict: # 등록되어있다면 false를 반환한다.
                return False
    return True # 끝까지 없다면 true 를 반환한다.