프로그래머스(Programmers) : 전화번호 목록 - python 풀이

🔴 전화번호 목록 문제 요약

전화번호 목록에 있는 여러 전화번호 중, 전화번호 A가 전화번호 B의 접두어인 경우가 없는지 판별하는 문제, ["12", "123"] 같이 전화번호 A가 전화번호 B의 접두어에 해당된다면 False를 반환, 그런 경우가 없다면 True를 반환하면 된다.

🟠 접근법

N은 1,000,000 이하이므로 O(NlogN)안에 해결해야한다.

phone_book에 대해 정렬을 수행하면 아스키 코드 순 -> 짧은 순으로 정렬이 되므로,
만약 한 번호가 다른 번호의 접두어라면, i-1번째 인덱스의 번호가 i번째 번호의 접두어일 것이다.

🟡 해결 코드

from typing import List

def solution(phone_book: List[str]) -> bool:
    phone_book.sort()                                   # 맨 앞 글자의 아스키 코드 오름차순 -> 짧은 순으로 정렬
    for i in range(1, len(phone_book)):                 # 만약 한 번호가 다른 번호의 접두어라면,
        if phone_book[i].startswith(phone_book[i-1]):   # i-1번째 인덱스의 번호가 i번째 번호의 접두어일 것이다.
            return False
        
    return True

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study

본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.