프로그래머스 전화번호 목록 풀이 With Python

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42577

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

이 문제는 정렬(sort)을 해야 효율적으로 풀 수 있습니다.

처음에는 시간 초과 때문에 통과를 못하였습니다. O(N^2)으로 풀어서 통과를 하지 못하였습니다.

하지만 sort를 통해 O(N)으로 풀 수 있었습니다. 문자열 순서로 오름차순으로 정렬을 한 뒤에 자신과 자신의 바로 다음 전화번호만을 비교하면 충분합니다. 아래는 소스코드입니다.

 

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

for 문을 통해 전체 전화번호(N)-1번 즉 O(N)에 문제를 해결하였습니다.

소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다. :-)