[python/해시] 25. 전화번호 목록(feat. startswith 함수)

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

  - 구조대 : 119

  - 박준영 : 97 674 223

  - 지영석 : 11 9552 4421

 

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

- phone_book의 길이는 1 이상 1,000,000 이하입니다.

- 각 전화번호의 길이는 1 이상 20 이하입니다.

 

입출력 예제

phone_book	return
['119', '97674223', '1195524421']	false
['123', '456', '789']	true
['12', '123', '1235', '567', '88']	false

 

---

나의 코드

def solution(phone_book):
    for i in range(len(phone_book)):
        for j in range(len(phone_book)):
            if i != j and phone_book[i].startswith(phone_book[j]):
                return False
    return True

for문을 두 개를 사용해서 한 번호가 다른 번호의 접두어인지 검사하는 코드를 짰다.

같은 문자열이 검사되는 경우를 막기 위해 if문에 i와 j는 같지 않다는 조건을 넣어줬다.

 

다른 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

여기서는 1) zip함수를 사용해서 서로 붙어 있는 문자열끼리 접두어인지 검사해주는 코드를 짰다.

그러면 멀리 떨어져 있는 문자열들은 어떻게 검사하지? 했는데,

2) sort를 해주면 접두어인 문자열끼리 알아서 붙게 정렬이 되기 때문에 문제가 되지 않는다.

생각해내기 어려운 방법이겠지만, 이렇게 작성하면 모든 문자열을 검사하는 것보다 효율성도 훨씬 좋다!

 

*startswith 함수

- str이 괄호 안에 있는 문자열로 시작하면 True, 아니면 False를 반환한다.