[Python/Programmers] 전화번호 목록

1. 난이도: 프로그래머스 Level 2

2. 문제요약: 요소간 서로의 접두사가 되는지 알안내기

3. 문제핵심: 시간 복잡도를 고려하면서 요소간 비교하기

코드

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

• sort()로 앞부분이 비슷한 애들로 정렬시켜준다.
• 어차피 서로의 접두사가 되는지 비교하는 것은 앞부분이 비슷한 요소들이 대상이기 때문이다.
• 따라서 startswith() 함수를 사용해 비슷하다 못해 아주 같은지 확인하다.
• 이때 비교는 모든 요소들과 할 필요가 없다.
• 한 요소와 그 요소 바로 전 것과만 비교하면 된다.
• 이미 정렬이 되어 있는 상태이기 때문에, 바로 앞 것이 접두사가 되지 못하는 상황이면, 그 어떤 것도 접두사가 되어주지 못한다.

느낀점

정렬은 강력하다!