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

문제

• N개 전화번호들 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하기
  • 1 <= N <= 1,000,000 
  • 접두어란,  한 번호 전체가 다른 번호 앞에 그대로 나오는 경우
  • 구조대 : 119
  • 지영석 : 11 9552 4421

 

풀이

• 각 번호에 대해서 모든 전화번호가 접두어인지 확인한다면 시간 초과
  • 시간 복잡도 : $O(NlogN)$
• 접두어인 번호가 있는지 없는지만 확인하면 되므로 전화번호를 정렬한 후, 자기 뒷 번호만 확인하면 된다.

 

""" 
- 접두어인 번호가 있으면 false
"""
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

 

References

• 프로그래머스 고득점 Kit 해시, 전화번호 목록