해시맵(HashMap)을 이용한 빈도 계산 알고리즘

1. 해시맵 (HashMap)

해시맵(HashMap)은 키(key)와 값(value)을 쌍으로 데이터를 저장하는 자료 구조입니다. 내부적으로 해시 함수(hash function)를 이용하여 키 값을 배열의 인덱스로 변환하여 저장합니다.

해시맵은 다음과 같은 특징을 가집니다.

빠른 조회 / 삽입 / 삭제가 가능합니다. 평균적으로 O(n)의 시간복잡도를 가집니다.
순서가 없습니다. 저장된 순서, 키의 정렬 등 특정한 순서를 가지지 않습니다. (Java에서는 순서가 필요한 경우, LinkedHashMap과 같은 자료구조를 사용할 수 있음)

1.1. 해시맵으로 빈도수 계산 방법

해시맵(HashMap)을 이용하여 빈도 계산하는 알고리즘은 주어진 배열, 문자열에서 각 원소가 몇 번 등장했는지 계산할 수 있는 대표적인 방법입니다. 시간복잡도 O(n)으로 한 번만 순회하여 계산할 수 있기 때문에 효율적입니다.

알고리즘의 기본 동작은 다음과 같습니다.

빈도를 저장하기 위한 해시맵 counts을 만듭니다.
데이터를 순회하며 현재 원소를 키 값으로 하여, 맵에 없으면 1로 초기화하고, 있으면 +1을 합니다
순회가 끝나면 counts에 각 원소의 개수가 저장됩니다.

data = [1, 2, 1, 3, 4, 5, 5, 5, 6, 7, 10, 3, 5, 8, 9, 8, 4, 5, 6, 2]
counts = {}
for x in data:
    if x in counts:
        counts[x] += 1  # 키 값이 있으면 +1을 함
    else:
        counts[x] = 1  # 키 값이 없으면 1로 초기화
print(counts)  # {1: 2, 2: 2, 3: 2, 4: 2, 5: 5, 6: 2, 7: 1, 10: 1, 8: 2, 9: 1}

python dict 자료구조의 get() 함수를 이용하여 위 코드를 더 간단하게 작성할 수 있습니다.

data = [1, 2, 1, 3, 4, 5, 5, 5, 6, 7, 10, 3, 5, 8, 9, 8, 4, 5, 6, 2]
counts = {}
for x in data:
    counts[x] = counts.get(x, 0) + 1
print(counts)  # {1: 2, 2: 2, 3: 2, 4: 2, 5: 5, 6: 2, 7: 1, 10: 1, 8: 2, 9: 1}

2. 예제 문제 풀어보기

2.1. 문자열의 문자 빈도 세기

문제

문자열 s가 있고, 각 알파벳의 개수를 출력합니다.

풀이

def solution(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts
 
 
s = "abracadabra"
print(solution(s))  # {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

2.2. 가장 빈도가 높은 요소 찾기

문제

입력으로 주어진 배열 nums에서 가장 빈도가 높은 요소를 출력합니다.

풀이

해시맵으로 빈도를 계산합니다.
등장 횟수를 기준으로 내림차순으로 정렬하여 첫번째 요소를 출력합니다.

def solution(nums):
    counts = {}
    for n in nums:
        counts[n] = counts.get(n, 0) + 1
    sorted_counts = sorted(counts.items(), key=lambda x: x[1], reverse=True)
    return sorted_counts[0][0]
 
 
nums = [1, 1, 1, 2, 2, 3, 3, 3, 3]
print(solution(nums))  # 출력: 3