[Programmers] 해시 - 전화번호 목록

1. 문제

• https://school.programmers.co.kr/learn/courses/30/lessons/42577

---

2. My Solution

2.1. Idea. any, startswith 이용

      

      

      

    
    

      <python />
    
def solution(phone_book):
    '''
    string 에서 subset 확인 
    '''
    for phone in phone_book:
        if any(other_phone.startswith(phone) for other_phone in phone_book if other_phone != phone):
            return False
        
    return True

• 다른 전화부를 비교하는데 오버헤드 발생

---

3. Other’s Solution

• https://school.programmers.co.kr/learn/courses/30/lessons/42577/solution_groups?language=python3

3.1. Idea 1. 정렬을 이용한 풀이

⇒ 어떻게 비교 횟수를 줄일 수 있을까?
문자열 정렬을 이용시, 접두사 앞 뒤로 위치
즉, phoneBook[i] 와 phoneBook[i+1] 만 비교하면 된다.
ex. [“119”, “97674223”, “1195524421”,”118”] ⇒ [“118”, “119”, “1195524421”, “97674223”, ]

      

      

      

    
    

      <python />
    
def solution(phoneBook):
    phoneBook.sort()

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

• sort, zip, startswith 이용
  • zip() 을 이용하여 phoneBook[i] 와 phoneBook[i+1] 쌍을 만든다.

3.2. Idea 2. Hash 를 이용한 풀이

      

      

      

    
    

      <python />
    
def solution(phone_book):
    answer = True
    hash_map = set(phone_book)

    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                return False
    return answer

• Idea : “1195524421” ⇒ “1”, “11”, “119” … 의 값이 있는지 확인하자.
  • 이 아이디어가 유효한 이유 : phone_number 가 20 자리로 한정되어 있다.
  • in 키워드를 이용해 빠르게 O(1) 값이 있는지 확인이 가능하다.