💡문제 분석 요약

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인한다.

접두어가 있으면 false, 없으면 true를 반환한다.

입출력 예제

💡알고리즘 설계

1. 짧은 번호가 접두어가 먼저 되므로 phone_book을 소트한다
2. for문을 이용해 해당 번호가 다른 번호의 접두어인지 확인

💡코드

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

for문을 중복해서 만든 코드.

정확성 테스트는 모두 맞았는데 효율성 테스트는 테스트3과 테스트4에서 시간 초과가 났다.

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

수정해서 맞은 코드

💡시간복잡도

전화번호부 소트→O(NlogN)

for문으로 비교→O(N)

⇒O(NlogN)

💡 틀린 이유

비효율적으로 모든 전화번호를 다 탐색했다.