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

목차

문제

프로그래머스

내코드

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

만약에 전화번호가 ["999","123","12345"] 라고 할 때, 정렬을 하면 ["123","12345","999"] 로 "!23"을 prefix로 가지고 있는 "!2345"는 "123"의 뒤에 위치하게 된다.

 

따라서 정렬을 한 뒤, 앞 뒤 요소만 비교를 하는 방식으로 문제를 해결하였다. 

 

오류코드1 (시간초과)

phone_book을 요소 길이 순으로 정렬한 뒤에, 문자열을 비교하는 방식으로 코드를 작성했는데 시간초과가 발생하였다. 

def solution(phone_book):
    flag = True
    phone_book.sort(key=len)
    book = [] 
    
    for new_num in phone_book:
        for num in book : 
            if new_num[:len(num)] == num:
                flag = False
                exit(0)
        book.append(new_num)
            
    return flag

 

오류코드2 

길이 순으로 정렬 + 문자열 슬라이싱이 문제인가 싶어서 일반 정렬 & 문자열 슬라이싱 대신 startswith를 사용하였지만, 여전히 test3&4 시간 초과가 발생하였다. 아무래도 중첩 for문을 사용한 것이 문제인 듯 하다. 

def solution(phone_book):
    flag = True
    book = [] 
    phone_book.sort()
    for new_num in phone_book:
        for num in book : 
            if new_num.startswith(num):
                flag = False
                break
        if (flag == False):
            break
        book.append(new_num)
        
    
    return flag

 

다른 사람 코드

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

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