해쉬맵(HashMap)과 해쉬셋(HashSet)

1. 해쉬맵(HashMap)

키(Key)와 값(Value)의 쌍으로 이루어진 자료구조.
특정 키에 대한 값을 빠르게 찾을 수 있음.
중복 키를 허용하지 않으며, 중복된 키가 삽입되면 기존 값을 덮어씀.
내부적으로 해싱(Hashing) 기법을 사용하여 빠른 검색, 삽입, 삭제를 가능하게 함.

hash_map = {}  # 딕셔너리 선언

# 값 추가
hash_map["apple"] = 3
hash_map["banana"] = 5

# 값 조회
print(hash_map["apple"])  # 3

# 값 변경
hash_map["apple"] = 10
print(hash_map["apple"])  # 10

# 키 존재 여부 확인
print("banana" in hash_map)  # True

# 값 삭제
del hash_map["banana"]
print(hash_map)  # {'apple': 10}

2. 해쉬셋(HashSet)

중복을 허용하지 않는 데이터 구조.
값 자체를 저장하며, 빠른 탐색, 삽입, 삭제가 가능.
내부적으로 해싱(Hashing) 기법을 사용.

hash_set = set()  # 집합 선언

# 값 추가
hash_set.add(1)
hash_set.add(2)
hash_set.add(3)
hash_set.add(3)  # 중복 값 추가 -> 무시됨

print(hash_set)  # {1, 2, 3}

# 값 존재 여부 확인
print(2 in hash_set)  # True

# 값 삭제
hash_set.remove(2)
print(hash_set)  # {1, 3}

해쉬맵과 해쉬셋으로 문제 풀기를 연습하려고 gpt에게 문제를 만들어달라고 했다.

<문제1>

한 전화번호가 다른 전화번호의 접두어인 경우 False, 접두어 관계가 없다면 True 출력

phone_book = ["119", "97674223", "1195524421"]

def check(lst):
    hash_map = {phone : True for phone in phone_book}
    
    for phone in phone_book:
        temp = ""
        for num in phone:
            temp += num
            if temp in hash_map and temp != phone:
                return False
            
    return True
    
check(phone_book)

<문제2>

• 주어진 문자열 s의 서로 다른 부분 문자열 개수를 구하라.
• 부분 문자열이란 연속된 문자들의 일부를 의미한다.
• 예를 들어, "ababc"의 부분 문자열은 "a", "ab", "b", "ba", "c", "ababc" 등이 있다.
• 같은 부분 문자열은 한 번만 세어야 한다.

s = "ababc"

def count(text):
    cnt = 0
    hash_map = {}
    
    subtext = ""
    for i in range(0, len(text)):
        for j in range(i+1, len(text)+1):
            subtext = text[i:j]  #subtext += text[i:j] 연산이 O(N)
            if subtext in hash_map:
                hash_map[subtext] += 1
            else:
                hash_map[subtext] = 0
        
    return len(hash_map)

이 문제는 해쉬맵으로 풀었지만, value값이 없어도 된단 생각에 다시 풀었다.

def count1(text):
    cnt = 0
    hash_set = set()
    
    for i in range(0, len(text)):
        for j in range(i+1, len(text)+1):
            hash_set.add(text[i:j])
        
    return len(hash_set)

해쉬맵에서 해쉬셋으로 수정하면서 subtext 변수도 없앴다.

위의 두 코드 모두 시간 복잡도가 O(N³)이다. 따라서 트라이(Trie)를 사용해 시간 복잡도를 O(N² log N),까지 줄일 수 있다고 한다. 이 자료구조는 다음에 공부해 보겠다.