해시_PRO#42577 : 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예제

 

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

---

Sol ) 시간초과

처음에는 전화번호들이 들어있는 리스트를 정렬하지 않아 틀린 테스트케이스가 발생했다.

["97674223", "1195524421","119"] 과 같이 들어있다면 "1195524421"의 길이가 "119"보다 길어서 False를 반환하지 못하기 때문이다.

 

그래서 정렬을 하였을 때는 모든 테스트 케이스를 통과하였지만 효율성 테스트에서 시간초과 문제가 발생하였다.

def solution(phone_book):
    phone_book = sorted(phone_book)
    
    while phone_book:
        num = phone_book.pop(0)
        
        for left_num in phone_book:
            if len(left_num) > len(num) and left_num[:len(num)] == num:
                return False
    
    return True

 

Sol)

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

앞선 시간 초과 문제에서는 [0]을 [1],[2],...[n] 번호들과 비교하고, [1]을 [2],[3],...,[n] 번호들과 비교했지만

사실 정렬을 하면 [0]과 [1]을 비교하면 [0]과 [2]를 비교할 필요는 없다. [0]이 [2]의 접두어였다면, [1]도 [2]의 접두어이기 때문이다. (숫자를 정렬하는게 아니라 "1020"와 같이 문자열을 정렬했기 때문)

따라서 시간초과 문제를 해결할 수 있다.

 

 

Sol) Hash

phoneBook의 모든 번호를 Hashing 해두고 나서 접두어 찾는 방식이다.

 

def solution(phone_book):
    answer = True
    hash_map = {}
    
    # 모든 전화번호가 HashMap에 등록
    for number in phone_book:
        hash_map[number] = 1
    
    # substring을 떼어서, HashMap에 존재하는지 확인
    for number in phone_book:
        temp = ""
        for num in number:
            temp += num
            if temp in hash_map and temp != number:
                answer = False
    
    return answer