[Python] (해시) 전화번호 목록

문제 설명

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

• 구조대 : 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

 

코드 작성

실패 # 1

def solution(phone_book):
    phone_book.sort()
    count = 0
    for i in range(len(phone_book)):
        for s in phone_book:
            if phone_book[i] in s[0:len(phone_book[i])]:
                count += 1
        if count >= 2:
            return False
        count = 0
    return True

이번에도 정확도는 맞았는데 효율성에서 틀렸다.

s에 phone_book의 원소를 넣고, s의 접두사만 비교하도록 했는데

이게 시간이 너무 오래걸리는 것 같다.

 

성공 #1

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book) - 1):
        if phone_book[i] in phone_book[i + 1][0:len(phone_book[i])]:
            return False
    return True

생각해보니 왜 굳이 s에 대입해서 넣었나싶다.

그냥 phone_book에서 i번째 원소에서 i+1번째 원소의 접두사만 확인하면 되는 거였다.

그러니까 코드도 간결해지고 속도도 매우 빨라졌다.. 그런데 아직 효율성 테스트가 간당간당하긴 하다.

 

대다수의 정답

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

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

우선 전화번호를 숫자가 1111111처럼 1이 많은 순서부터 차례대로 정렬한다.

예를 들면 아래와 같이 정렬된다.

phone_book = ["119", "97674223", "11295524421", "2313131", "1111111", "11915154844"]
phone_book.sort()

['1111111', '11295524421', '119', '11915154844', '2313131', '97674223']

 

그리고 p1에는 처음부터 끝까지, p2에는 2번째부터 마지막까지를 차례대로 대입한다.

list.startswith() 함수(list에 단어가 포함되면 True를 반환)를 사용하여 조건문을 만든다.

 

끝으로

분발하자