전화번호 목록

📖 해시 > 전화번호 목록

📖What I thought

• 어떻게 확인하지?

1. 2중 for문 돌아보기 → 시간 초과 에바일 듯 ;;
2. 전화번호들을 dictionary에 넣어서 체크해보자
3. phone_book 정렬 후 for문 돌아보면서 idx 붙어있는 전화번호 비교해보자 (낙찰✔️) → 전화번호는 숫자로 이루어진 문자열 → 문자열 정렬은 숫자로써가 아닌 문자열을 사전순으로 나열 '1', '10', '5' → 다른 전화번호의 접두어라면 idx 붙어있을 것

📖풀이

📎Dictionary

def solution(phone_book):
    hs = {p:1 for p in phone_book} # 전화번호북
 
    for phone in phone_book:
        prep = ''
 
    # 번호 뜯어서 접두사 맹들기
        for p in phone:
            prep += p
 
    # 현재 폰 번호 아니면서 다른 폰 번호인 상황 == 한 번호가 다른 번호의 접두어인 경우
            if prep in hs and prep != phone:
                return False
 
    return True

• 모든 전화번호를 해싱하자 → 모든 전화번호가 해시 테이블(hs)에 저장됨
• 이제 각 전화번호의 접두어가 해시 테이블에 존재하는지 확인하기
• 어떻게? 각 전화번호를 앞에서부터 뜯어서 해시 테이블에 존재하한다면 접두어 존재하는 것
• 🚨 해시 테이블에는 모든 전화번호가 들어 있으므로 자기 자신인 경우 제외해야 함

📎startswith()

def solution(phone_book):
    phone_book.sort()
    
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
 
    return True

• phone_book 정렬을 하면 앞 뒤로 비교할 필요 없으니까 시간 단축 가능
• …이것까지는 생각했는데 startswith() 메소드라는 아주 좋은 메소드가 있었음!

📖What I learned

1. startswith() 에 대해 알게 되었따!
2. 문자열을 요소로 가진 리스트를 정렬하면 문자열을 사전순으로 나열(알고 있지만 착각하기 쉬움)

📖관련 지식

📎Hash Table

📎startswith()