해시 데이터 구조의 적용 사례와 최적화 기법
알고리즘 문제를 해결하는 과정에서 특정 원소의 존재 유무나 빈도수를 빠르게 확인해야 하는 상황은 매우 흔합니다. 이때 단순한 나열된 데이터를 순회하며 비교하는 방식은 시간 복잡도가 O(N^2)에 달할 수 있어 비효율적입니다. 이러한 경우 선형 시간인 O(1) 검색 성능을 제공하는 해시 테이블 (HashMap 또는 Set) 을 활용하는 것이 표준적인 접근 방법입니다.
1. 표적 합 (Two Sum) 문제
특정 두 개의 숫자가 더해져 목표값과 일치하도록 인덱스를 찾는 문제입니다. 초기에는 이중 반복문을 사용한 브루트 포스 방식이 가능하나, 탐색 속도를 높이기 위해 사전에 방문한 값을 저장하고 현재 값과 필요한 값을 조합하여 검증하는 방식이 권장됩니다.
Java 구현 예시
입력 배열의 각 요소마다 타겟 차이치를 계산하여, 이전 단계에서 저장된 해시맵에 해당 키가 있는지 확인합니다.
class Solution {
public int[] findIndices(int[] dataArray, int searchTarget) {
int[] answer = new int[2];
if (dataArray == null || dataArray.length == 0) {
return answer;
}
// 값을 키로, 인덱스를 값으로 매핑
Map lookupMap = new HashMap<>();
for (int idx = 0; idx < dataArray.length; idx++) {
int requiredValue = searchTarget - dataArray[idx];
if (lookupMap.containsKey(requiredValue)) {
answer[0] = idx;
answer[1] = lookupMap.get(requiredValue);
return answer;
}
lookupMap.put(dataArray[idx], idx);
}
return answer;
}
} - 주의사항: 기본 타입
int의 길이는 메서드 호출 없이.length로 접근하며, 해시맵의put연산이 결과 도출 이후에도 수행되지 않도록 반환 위치를 조정합니다.
Python 구현 예시
딕셔너리를 사용하여 동일 로직을 표현합니다. 중복 처리를 위해 조건 체크를 명확히 합니다.
class Solver:
def twoSum(self, numbers, goal):
"""
:type numbers: List[int]
:type goal: int
:rtype: List[int]
"""
if not numbers:
return []
# 키: 숫자, 값: 인덱스 저장용 딕셔너리
recorded_map = {}
for current_index, value in enumerate(numbers):
complement = goal - value
if complement in recorded_map:
return [recorded_map[complement], current_index]
recorded_map[value] = current_index
return []2. 문자열 묶기 (Group Anagrams)
단어의 알파벳 조합만 다르더라도 구성하는 글자가 같다면 동일한 그룹에 속합니다. 이를 구분하기 위해서는 각 문자열을 정렬했을 때 나오는 결과를 공통 키 (Key) 로 사용하는 방식이 효과적입니다.
Java 구현 예시
문자열을 정렬하여 생성된 새로운 문자열을 키로 설정하고, 원래 문자열을 리스트에 담아 매핑합니다.
import java.util.*;
class AnagramGroup {
public List categorize(String[] words) {
Map grouping = new HashMap<>();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String sortedKey = new String(chars);
// 기존에 키가 있으면 리스트 가져오기, 없으면 새 리스트 생성
List<String> groupList = grouping.computeIfAbsent(sortedKey, k -> new ArrayList<>());
groupList.add(word);
}
return new ArrayList<>(grouping.values());
}
} Python 구현 예시
collections 모ジュール 의 defaultdict 를 활용하면 키가 없을 때 자동으로 빈 리스트를 생성하므로 코드가 간결해집니다.
import collections
def group_anagrams(words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
table = collections.defaultdict(list)
for st in words:
# 정렬된 문자들을 문자열로 변환하여 키 생성
# sorted() 는 리스트를 반환하므로 join 으로 연결 필요
key = "".join(sorted(st))
table[key].append(st)
return list(table.values())- 핵심 포인트:
"".join()함수는 리스트를 문자열로 변환할 때 사용되며, 정렬된 문자들이 불변 객체가 되어야 딕셔너리의 키로 사용할 수 있습니다.
3. 연속된 최대 길이 찾기
배열 내에서 가장 긴 연속된 정수 열의 길이를 구하는 문제입니다. 무작위 정렬된 배열에서도 효율적으로 해결하려면 정렬을 피하고 집합 (Set) 기반의 탐색을 사용합니다.
각 원소를 기준으로 그보다 작은 전단계 숫자가 존재하는지 확인합니다. 만약 num-1 이 있다면 현재 숫자는 연속성 시작점이 아니므로 스킵하고, 없다면 여기서부터 다음 연속된 숫자를 찾아냅니다.
Java 구현 예시
public class ConsecutiveSequence {
public int findMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// 중복 제거 및 빠른 검색을 위한 HashSet 생성
Set<Integer> numberSet = new HashSet<>();
for (int num : nums) {
numberSet.add(num);
}
int maxLen = 0;
for (int num : numberSet) {
// 현재 숫자가 연속된 수열의 시작인지 확인
if (!numberSet.contains(num - 1)) {
int currentNum = num;
int currentLen = 1;
// 후속 숫자가 있는 동안 증가
while (numberSet.contains(currentNum + 1)) {
currentNum++;
currentLen++;
}
maxLen = Math.max(maxLen, currentLen);
}
}
return maxLen;
}
}Python 구현 예시
def longest_consecutive_sequence(nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
unique_nums = set(nums)
longest_count = 0
for n in unique_nums:
# 수열의 시작점인지 판별
if (n - 1) not in unique_nums:
current_value = n
current_count = 1
while (current_value + 1) in unique_nums:
current_value += 1
current_count += 1
longest_count = max(longest_count, current_count)
return longest_count- 최적화 논리: 모든 원소에 대해 다음 원소가 존재하는지 계속 검사하지 않고, 해당 숫자의 전진 수가 없는 경우에만 내부 While 루프를 실행함으로써 전체 시간복잡도를
O(N)수준으로 유지할 수 있습니다.