99클럽 코테 스터디 5일차 TIL + 해시

오늘의 문제 - 해시

문제 설명

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

입출력 예제

---

내 풀이 및 접근 방식

91.7 오답, 효율성 테스트에서 시간 초과

def solution(phone_book):
    answer = True
    
    phone_book.sort(key=lambda x : len(x))
    
    for i in range(len(phone_book)-1):
        for j in range(i+1, len(phone_book)):
            if phone_book[i] == phone_book[j][:len(phone_book[i])]:
                answer = False
                break
                
        if not answer:
            break
    
    return answer

 

풀이 방식

1. 전화번호부를 전화번호 길이 순으로 정렬한다. 
2. 순서대로 번호를 순회하며 뒤 번호의 순서들 중 접두어인 번호가 있는지 찾는다.
3. 하나라도 접두어가 동일한 번호가 발견되면 break

시간 복잡도

1. 정렬: O(n*logn)
2. 이중 for 루프 부분: O(n^2*m)
   바깥쪽 루프는 n-1번 실행, 안쪽 루프는 n-i-1번 실행 => 이중 루프의 반복 횟수는 (n-1)n/2로 O(n^2)
   루프 내의 비교 연산은 최대 전화번호 길이 m에 비례하므로, 최악의 경우 O(m)

---

다른 풀이

1. for문 하나로 구현하는 방법

길이로 정렬하지 않고, 사전 순으로 정렬하면 앞뒤로 동일한 접두어가 배치되기 때문에 i와 i+1만 비교해주면 된다.

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            answer = False
            break
            
    return answer

 

시간 복잡도

1. 정렬: O(n*logn)
2. 루프 부분: O(n*m)

2. 해시 이용 방법

파이썬에서는 dictinoary가 hash map 자료 구조이고, 탐색, 삽입, 삭제의 시간복잡도가 O(1)인 특징이 있다.

def solution(phone_book):
    hash_map = {}
    for phone_num in phone_book:
        hash_map[phone_num] = 1
    
    for phone_num in phone_book:
        prefix = ""
        for num in phone_num:
            prefix += num
            if prefix in hash_map and prefix != phone_num:
                return False
    return True

# 출처: https://coding-grandpa.tistory.com/86 [개발자로 취직하기:티스토리]

 

풀이 방식

1. key를 전화번호로 하고, value를 1로 하여 hasp_map에 전화번호를 추가한다.
   ex) hash_map = {('010', 1), ('3425', 1), ... }
2. 전화번호부를 순회하며, 접두어를 생성하고 생성된 접두어에 번호를 하나씩 더하고, 접두어가 hash_map에 있는지 확인한다.

시간 복잡도

1. hash map 설정: O(n)
2. 접두어 검사: O(n*m)
   전화번호부 순회는 O(n)이 소요되고, 모든 길이의 전화번호가 m인 경우로 가정할 때 2번째 for문에서 O(m) 시간이 소요된다. if 문 시간 복잡도는 O(1)(해시 맵에서의 키 조회 연산)+O(m)(문자열 비교 연산)으로 O(m)이다.

---

회고

해시맵(딕셔너리)

• key와 value 값을 쌍으로 값을 저장하는 자료구조
• 해싱을 기반으로 하여 탐색, 삽입, 삭제 시간복잡는 O(1)
• 사용법

# 선언
hash_map = dict()
hash_map2 = {}

# 삽입
hash_map[key] = value

# 탐색
if key in hash_map: # key 탐색
if value in has_map: # value 탐색

# 삭제
hash_map.pop(key, None) # 2번째 인자 None 넣어주면 key가 존재하지 않아도 error 발생 안함
del hash_map[key]

# 출력
print(hash_map) # 전체 출력 {'119': 1, '97674223': 1, '1195524421': 1}
print(hash_map.items()) # 전체 출력 dict_items([('119', 1), ('97674223', 1), ('1195524421', 1)])
print(hash_map.keys()) # 모든 key 출력 dict_keys(['119', '97674223', '1195524421'])
print(hash_map.values()) # 모든 value 출력 dict_values([1, 1, 1])