[프로그래머스][hash] 전화번호목록 python (200715)

1. 문제 

문제 설명

 

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

 

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

 

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

 

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

 

입출력 예제

phone_book   return

[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

입출력 예 설명

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

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

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

 

 

2. 풀이 

 

1) hash (dictionary) 없이 문자열 startswith() 로 쓰는 법

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

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

 

이렇게 봤을 때는 왜 굳이 해쉬를 써야하는지 이해가 가질 않았다. 

물론 위 코드처럼 풀어도 되지만, 굳이 해쉬를 써봄으로서 해쉬의 필요성을 알아보겠다. 

 

 

 

2) hash 를 사용하는 방법. 

def solution(phone_book):
    answer = True
    hash_map = {}
    
    # 등장한 숫자들을 count 딕셔너리로 만듦
    for phone_number in phone_book:
        hash_map[phone_number] = 1
        
    # 다시 숫자들을 꺼낸뒤
    for phone_number in phone_book:
        temp = ""
        for number in phone_number: #숫자 하나씩 뜯어보기
            temp += number
            #딕셔너리 키로 같은게 있지만! 전체 숫자는 다른 경우!
            if temp in hash_map and temp != phone_number:
                answer = False
                
    print(hash_map)
    return answer

 

하지만 여기서 굳이 hashmap 을 만들지 않고, 

리스트와 바로 비교를 하는 코드로 바꾸는게 낫지 않을까? 라 생각을 했다 그래서 그렇게 작성한 결과! 

 

 

 

2) 번외1 - 위에 코드에서 hash 없이 list 로 비교하기 

def solution(phone_book):
    answer = True
    hash_map = {}

    for phone_number in phone_book:
        temp = ""
        for number in phone_number:  # 숫자 하나씩 뜯어보기
            temp += number

            if temp in phone_book and temp != phone_number: # 딕셔너리 리스트로 바꿈
                answer = False

    return answer

 

시간초과였다 그 이유를 찾아보면

리스트를 탐색하는 경우 o(n) 의 복잡도가 걸리지만, 딕셔너리를 탐색하는 경우 o(1)로 복잡도가 줄기 때문에! 

리스트는 containment (포함여부를 체크하는 in 구문) 을 하는데 선형 탐색을 해서다. 

https://gomguard.tistory.com/181

[Python] List, Dict 시간 복잡도 (Big O)

++)) 여기서 하나더 궁금해진 것은 그럼 dict.keys() 로 했을 때는 어떨까? 

 

2) 번외 2- dict 과 dict.keys()로 했을 때의 차이 

마찬가지로 keys() 를 해도, 통과가 된다. 

하지만 둘의 연산 속도는 차이가 있다고 하는데 

아래의 글을 살펴보면  temp in hasp_map 의 연산 속도가  

temp in hasp_map.keys() 보다 조금 빠른걸 확인 할 수 있다. 

https://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity

Python dictionary keys. "In" complexity

 

3. 정리 

앞으로 list 탐색 오래 걸려서 런타임 에러뜰때 해쉬로 접근해봐야겠다....!!!!