해시 테이블 사용 예제 문제

8.1 배열에서 중복 찾기

문제: 숫자 배열이 주어졌어. 배열에서 모든 중복을 찾아 반환해야 해.

해결방법: 이미 등장한 숫자를 추적하기 위해 해시 테이블을 사용해. 숫자가 다시 등장하면, 그걸 중복 리스트에 추가해.

구현 예제:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 사용 예제
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # 출력: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # 출력: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # 출력: []

설명:

• 고유한 숫자를 추적하기 위해 빈 집합 seen을 만들어.
• 배열의 각 요소를 순회해. 만약 seen에 요소가 이미 존재하면, 그걸 duplicates 리스트에 추가해.
• seen에 요소가 없으면, 그걸 추가해.
• 중복 리스트를 반환해.

빈 배열과 중복이 없는 배열 모두에 대해 함수가 올바르게 작동하여 둘 다 빈 리스트를 반환하는 걸 확인할 수 있어.

8.2 애너그램 확인 문제

문제: 두 문자열이 주어졌어. 이들이 애너그램 (동일한 개수의 동일한 문자를 포함하는지)인지 확인해야 해.

해결방법: 두 문자열에서 문자의 빈도를 세고 결과를 비교하기 위해 해시 테이블을 사용해.

구현 예제:

def are_anagrams(str1, str2):
    # 대소문자를 무시하기 위해 문자열을 소문자로 변환해
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # 첫 번째 문자열의 문자 빈도 계산
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # 두 번째 문자열의 문자 빈도 차감
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # 모든 값이 0인지 확인
    return all(count == 0 for count in char_count.values())

# 사용 예제
print(are_anagrams("listen", "silent"))  # 출력: True
print(are_anagrams("hello", "world"))  # 출력: False
print(are_anagrams("", ""))  # 출력: True
print(are_anagrams("Tea", "Eat"))  # 출력: True

설명:

• 문자열의 길이가 일치하지 않으면 애너그램이 될 수 없어.
• 첫 번째 문자열의 문자 빈도를 세기 위해 char_count 사전을 사용해.
• 두 번째 문자열을 순회하며 문자 빈도를 차감해.
• 모든 사전 값이 0인지 확인해. 그렇다면 문자열은 애너그램이야.

문자열을 비교하기 전에 소문자로 변환해서 대소문자를 무시하는 걸 유의해. 또한, 빈 문자열을 서로 애너그램으로 간주하여 올바르게 처리하는 걸 확인해.

8.3 특정 합을 가진 쌍 찾기 문제

문제: 숫자 배열과 목표 합계 값이 주어졌어. 합쳐서 목표 값을 주는 모든 숫자 쌍을 찾아야 해.

해결방법: 해시 테이블을 사용하여 숫자를 저장하고 현재 숫자와 함께 목표 합계를 이루는 쌍이 있는지 확인해.

구현 예제:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# 사용 예제
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 출력: [(1, 5), (1, 5)]

설명:

• 숫자를 추적하기 위해 빈 집합 seen을 만들어.
• 배열의 각 숫자에 대해 목표 합계에서 현재 숫자를 빼서 그 보완 값 complement을 계산해.
• 보완 값이 seen에 존재하면, 쌍 (complement, num)을 pairs 리스트에 추가해.
• 현재 숫자를 seen에 추가해.
• 쌍 리스트를 반환해.

이 알고리즘은 배열의 요소 수인 n에 대해 시간 복잡도가 O(n)이라는 점이 중요해. 이는 두 개의 중첩된 루프를 사용하여 시간 복잡도가 O(n^2)인 단순한 방법보다 훨씬 효율적이야. 해시 테이블을 사용하면 배열을 한 번만 순회하여 모든 쌍을 찾을 수 있어, 이는 대용량 데이터 처리 시 특히 중요해.

비교를 위해, 시간 복잡도가 O(n^2)인 단순한 해결방법은 다음과 같아:

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# 사용 예제
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # 출력: [(1, 5), (1, 5)]

이처럼 단순한 방법은 두 개의 중첩된 루프를 필요로 해서 큰 배열에서는 비효율적이야. 해시 테이블을 사용한 해결책이 같은 목표를 훨씬 빠르게 달성할 수 있어.