[프로그래머스][해시] 전화번호 목록

 

 

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

문제는 풀었는데 다른사람이 파이썬 내장함수로 한줄로 푸는거 보고 충격... 정리 따로 해야겠다.

 

아이디어는 이렇다.

 

• 전화번호부로 set을 이용해 hash테이블을 만든다.
• 각번호를 순회하면서 이중포문을 통하여 번호의 부분문자열을 얻은뒤 hash 테이블에 있는지 확인한다.
• hashtable에 있다면 누군가의 접두어가 된다는 뜻이므로 False를 리턴한다

이렇게 하면 시간복잡도는 1000000*20 이 되므로 충분히 통과한다

def solution(phone_book):
    mySet = set(phone_book)
    for i in phone_book:
        length = len(i)
        for j in range(1,length):
            if i[:j] in mySet:
                return False
    return True

 

 

아래는 파이썬 스타일로 푸는 방법이다.

 

• 정렬을 한다
• zip을 이용하여 인덱스를 한칸씩 밀어 요소들을 짝지어준다
• 나중에 오는 문자가 앞에 오는 문자로 시작하는지 확인한다.

 

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