[Python] 해시_전화번호 목록(2단계)

문제 설명

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

구조대 : 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입니다.

풀이 1

zip 함수

print(list(zip([1,2,3], (4,5,6), "abcd")))
[[1, 4, 'a'], [2, 5, 'b'], [3, 6, 'c']]

startswith 함수

# startswith는 꽤 직관적인 함수로 p2가 p1으로 시작되면 True 아니면 False를 반환한다.

print("dfagd".startswith("abcd"))
print("abcde".startswith("abcd"))
### False
### True

위의 개념을 이용한 풀이

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

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

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

위에 코드에서 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

해쉬 구조
링크텍스트

Hash Table

: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

알아둘 용어

해쉬(Hash)

: 임의 값을 고정 길이로 변환하는 것

해쉬 테이블(Hash Table)

: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

해싱 함수(Hashing Function)

: Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address)

: Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음

슬롯(Slot)

: 한 개의 데이터를 저장할 수 있는 공간
저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

장점

데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

단점

일반적으로 저장공간이 좀더 많이 필요하다.
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

주요 용도

검색이 많이 필요한 경우
저장, 삭제, 읽기가 빈번한 경우
캐쉬 구현시 (중복 확인이 쉽기 때문)

📢 hash table 만들기

hash_table = list([i for i in range(10)])
print(hash_table) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# list comprehension 예시
# 위 코드의 출력표현식을 i에서 i*i로 바꾼 결과

hash_table = list([i*i for i in range(10)])
print(hash_table) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# 종류가 다른 데이터에서 정수 리스트만 가져오기
dataset = [False, 49, "seunghye", 31.43, 6, 10]
int_data = [num for num in dataset if type(num)==int]
print(int_data) # [49, 6, 10]