프로그래머스 level2 [전화번호 목록] 파이썬

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3

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

시도1: 실패 (시간초과 풀이)

#프로그래머스 전화번호 목록
def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(i+1,len(phone_book)):
            leng=len(phone_book[i])
            if leng<len(phone_book[j]) and phone_book[i][0]==phone_book[j][0] and  phone_book[i]==phone_book[j][:leng]:
                return False
    return True

맨처음에는 이중 for문을 사용하여 버블소트 처럼 모든 항목을 하나씩 검사하려고했었다. 시간초과가 발생하였다.

 

생각해보니 어짜피 sort()하면, 문자열 기준으로 정렬되기때문에 굳이 이중 for문을 쓸 필요가 없다는 것을 깨달았다.

 

시도2: 성공

#프로그래머스 전화번호 목록
def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        leng1=len(phone_book[i])
        leng2=len(phone_book[i+1])
        if leng1<leng2 and phone_book[i]==phone_book[i+1][:leng1]:
            return False
    return True

O(N)의 시간복잡도로 해결하였다.

 

 

다른 사람의 풀이

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

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

p1은 0번째 index부터, p2는 1번째 index부터 시작해서 startswith이라는 함수를 이용하여 판단한다.