[프로그래머스] 전화번호목록

문제

프로그래머스 전화번호목록

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

프로그래머스

 

처음 코드

def solution(phone_book):
    for choice_phonephone in phone_book:    # 폰번호 선택
        for phone in phone_book:            # 비교할 폰번호
            if choice_phonephone == phone:  # 비교할 폰번호가 자신폰번이면 패스
                continue
            if choice_phonephone in phone:
                return False
    return True

1. 처음엔 배열을 이용한 완전탐색 방법으로 풀었다.
2. 기준 폰번호를 선택하고, 전화번호부를 모두 돌아가며 비교할 폰번호를 선택하고 이와 비교한다.
3. 기준 폰 번호의 문자열이 비교할 폰번호에 포함되어있다면 False를 반환하고
4. 기준 폰 번호와 비교할 폰번호가 같다면 건너뛴다.
5. 모두 탐색을 마쳤는데도 기준 폰번호의 문자열이 비교 폰번호에 포함된적이 없다면 True를 반환한다.

 

문제점

이렇게 풀면 매우 간단하지만, 시간복잡도가 어마무시해진다. 시간복잡도를 줄이기 위해 해시를 쓰면 좋다.

 

 

해시를 이용한 코드

def solution(phone_book): 

    # 해시맵 만들기
    hash_map = {} 
    for nums in phone_book: 
        hash_map[nums] = 1 
    
    # 접두어가 해시맵에 존재하는지 찾기 
    for nums in phone_book: 
        arr = "" 
        for num in nums: 
            arr += num
    
            # 본인일 경우 제외
            if arr in hash_map and arr != nums:       
                return False 
                
    return True

 

새롭게 배운점 / 느낀점

해시?

• 해시는 자료구조 중 하나다. 데이터가 키와 밸류 형식으로 형식화 되어있다( = 딕셔너리 구조)
• 키와 밸류를 맵핑하는 과정 자체를 해싱 이라고 한다.
• 배열을 쓸 수 없을때 해시가 좋다.
  • 배열은 arr[1], arr[2]등 숫자 인덱스로 원소를 접근하지만, 해시는 arr[’a’] 같이 문자 인덱스로 접근 할 수 있다.

• ⭐️빠른 접근/탐색이 필요할때 쓰면 좋은 자료구조다⭐️
  • 해시는 대부분의 동작이 O(1)의 시간 복잡도를 가진다.
  • 배열에서 원소를 넣거나 삭제할때는 시간복잡도가 O(1)~O(n)이지만, 해시는 원소 삽입/삭제시 O(1)의 시간복잡도를 가진다.
• 해시의 시간복잡도 워스트 케이스는 O(n)이다. 여러개의 키 값이 해시 함수로 같은 밸류를 가져서 충돌이 일어날때 O(n)의 시간복잡도를 가진다.
  • 충돌이 일어난 경우 선형탐색, 제곱탐색, 이중 해시로 해결 할 수 있다.
    • 선형탐색 : 충돌이 발생한 위치부터 하나하나씩 밸류 탐색
    • 제곱탐색 : 충돌이 발생한 위치부터 제곱만큼 떨어진 밸류 탐색(1, 4, 9, 16 …)
    • 이중해시 : 충돌 발생하면 다른 해시 함수를 한번더 적용

• 해시는 시간 복잡도가 작은 대신, 공간 복잡도가 크다.

 

• 해시의 존재만 알았지, 어떤 상황에서 쓰면 좋은지를 몰랐다.
• 해시는 탐색/삽입/삭제가 매우 빠르니 앞으로 그런 기능을 구현해야한다면 배열보다 해시를 먼저 생각해야겠다.