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

• 프로그래머스: 전화번호 목록 Level 2
• 문제링크

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

나의 접근

접근1: 큐로 풀었다가 시간 초과 에러 및 테스트케이스 3개를 통과시키지 못했다. 

def solution(phone_book):
    count = len(phone_book)
    while count > 0:
        num = phone_book.pop(0)
        for i in range(len(phone_book)):
            if num in phone_book[i]:
                return False
        
        phone_book.append(num)   
        count -= 1
    
    return True
        

 

접근2: 주어진 리스트를 길이대로 sort해서 앞에서부터 이중 for문으로 비교해주었다. 여전히 시간초과가 떴다 ㅠㅠ

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

 

 

접근3: 다른 풀이를 찾아보았는데, 왜 각 번호의 길이대로 sort하는게 아니라 숫자의 크기대로 sort 하는지 이해가 가지 않았다. 생각해보니 숫자의 크기대로 sort하게 되면 이렇게 정렬이 된다.

12, 123, 1231, 88 99

이렇게 되면 0번째 번호를 기점으로 그 다음 원소만 비교해주면 된다. 효율 면에서 개선이 된 코드이다.

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

이번엔 진짜 될 줄 알았는데.... 두둥.. 알 수 없는 테케 하나에서 또 패스가 되지 않는다..

자비좀...

 

접근4 (pass) : 찐막 도전이다. startswith() 함수를 사용한 방법이다. in을 사용하는 것보다 훨씬 효율적이라고 한다. zip과 startswith()에 대해서는 새로운 포스트로 다뤄보려 한다.

def solution(phone_book):   
    phone_book.sort()
    answer = True
    for x,y in zip(phone_book, phone_book[1:]):
        if y.startswith(x):
            answer = False
            break
    return (answer)