[프로그래머스/Python] 전화번호 목록

처음 풀었던 방법인데 효율성 테스트 3,4 에서 시간초과가 뜬 코드다

def solution(phone_book):
    p = []
    answer = True
    for num in sorted(phone_book, key = lambda x: len(x)):
        for prefix in p:
            if num[:len(prefix)] == prefix:
                answer = False
        else:
            p.append(num)
        
        if not answer:
            break

    return answer

startswith 도 써보고, 길이로 정렬이 아닌 그냥 문자열 정렬을 해주기도 했지만

계속 시간 초과가 나서

풀이 과정에 뭔가 생각의 전환이 필요함을 느꼈다!!

참고로 문자열 숫자 정렬은 숫자 크기가 아닌, 앞의 글자 숫자 크기로 정렬을 한다(내림차순이 디폴트)

ex) 119 1191231231 120 이렇게 정렬됨(1'1' > 1'2')

 

def solution(phone_book):
    phone_book.sort()
    answer = True
    
    # i+1의 prefix는 아닌데 i+2의 prefix 일 수는 없음!
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            answer = False
            break

    return answer

이중 for문으로 전체를 검사할 필요 없이 i와 i+1만 비교해주면 된다는 사실을 깨달았다.

 

 

시간 복잡도

정렬(합병정렬): O(nlogn)

for: O(n)

=> O(nlogn)

 

다른 사람 풀이

- zip을 이용해 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

-해시를 이용한 정석 풀이

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

핸드폰 번호를 일단 dict에 key로 다 넣는다.

그리고 다시 for문 돌면서 전화번호의 숫자 하나씩 추가하며 dict으로 검색한다. -> O(1)