[Programmers] Level 2. 전화번호 목록 (Python)

🔗 Problem Link

프로그래머스

---

❔Thinking

• 한 번호가, 다른 번호의 시작과 동일한 경우가 있다면 False, 하나도 없다면 True를 반환한다.

---

💻Solution

1. 모든 접두사를 확인하는 풀이

def solution(phone_book):
    phone_dict = {number : number for number in phone_book}
    for phone_num in phone_book:
        for i in range(1,len(phone_num)):
            if phone_num[:i] in phone_dict and phone_dict[phone_num[:i]] != phone_num:
                return False
    return True

 

2. startwith()를 활용한 풀이

def solution(phone_book):
    phone_book = sorted(phone_book)
    for num1, num2 in zip(phone_book, phone_book[1:]):
        if num2.startswith(num1):
            return False
    return True

---

🗝️keypoint

1. startwith()는 한 문자열이 다른 문자열의 시작과 동일한지 확인한다.
2. dictionary에서 key로 value를 조회하는 과정은 $O(n)$의 시간복잡도를 가진다.