Hash 문제 유형1: 존재여부 확인
배경 및 목표에 대해 1문장으로 기재
Hash 문제 유형: 존재 여부 확인
해시 테이블과 집합은 요소의 존재 여부를 빠르게 확인하는 데 매우 유용한 데이터 구조이다. 이러한 구조를 활용하면 배열 기반의 탐색에서 발생하는 성능 저하를 해결하고, 알고리즘의 시간 복잡도를 획기적으로 줄일 수 있다. 이번 내용에서는 해시를 활용한 문제 유형과 효율적인 풀이법을 살펴본다.
배열을 이용해 특정 요소가 존재하는지 확인하는 경우, 모든 요소를 순회해야 하므로 시간복잡도는 이다. 그러나 해시 테이블과 집합은 평균적으로 시간 복잡도로 탐색을 수행할 수 있다.
예제1 - two sum
정수 배열 nums와 정수 target이 주어졌을 때, 합이 target이 되는 두 숫자의 인덱스를 반환한다. 동일한 인덱스를 두번 사용할 수 없다.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9,
Plain Text
복사
풀이 1: 브루트포스 접근법 (시간복잡도: )
배열의 모든 요소 쌍을 비교하여 합이 target과 같은지 확인한다.
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
Python
복사
•
단점: 중첩된 루프를 사용하므로, 입력 배열이 클 경우 비효율적이다.
풀이 2: 해시 맵(시간복잡도: )
배열을 한 번 순회하면서, 각 숫자가 target을 만들기 위해 필요한 보완값(complement)이 해시 맵에 존재 하는지 확인한다.
def twoSum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map: # O(1)
return [hash_map[complement], i]
hash_map[num] = i
Python
복사
동작 원리
1.
hash_map은 배열의 값을 키(key), 인덱스를 값(value)으로 저장합니다.
2.
현재 숫자의 보완 값(target - num)이 hash_map에 있는지 확인합니다.
3.
있다면 두 수의 인덱스를 반환하고, 없다면 현재 숫자를 hash_map에 추가합니다.
시간 복잡도
•
해시 맵의 삽입과 조회는 평균적으로
•
배열을 한 번 순회하므로 전체 시간 복잡도는
공간 복잡도
•
해시 맵에 배열의 모든 요소를 저장하므로
예제2 - 2351.Fist Letter to Appear Twice
문자열에서 첫번째로 두 번 등장하는 문자를 반환한다.
Input: s = "abccbaacz"
Output: "c"
Explanation:
The letter 'a' appears on the indexes 0, 5 and 6.
The letter 'b' appears on the indexes 1 and 4.
The letter 'c' appears on the indexes 2, 3 and 7.
The letter 'z' appears on the index 8.
The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.
Python
복사
풀이 1: 브루트포스 (시간 복잡도: )
각 문자를 기준으로 문자열을 앞에서부터 탐색하여 중복 여부를 확인한다.
•
단점: 이중 루프를 사용하므로 문자열이 길어질수록 성능이 급격히 저하된다.
def repeatedCharacter(self, s: str) -> str:
for i in range(len(s)):
c = s[i]
for j in range(i):
if s[j] == c:
return c
Python
복사
풀이 2: 집합(set)을 활용한 효율적인 접근(시간 복잡도: )
문자를 순회하며 이미 등장한 문자를 set에 저장한다. 새로운 문자가 set에 이미 있다면 중복된 문자이다.
def repeatedCharacter(s):
seen = set()
for char in s:
if char in seen:
return char
seen.add(char)
Python
복사
동작 원리
1.
seen 집합에 각 문자를 추가한다.
2.
문자가 이미 seen에 있다면 중복된 문자로 간주하고 반환한다.
시간 복잡도
•
문자열을 한 번 순회하므로
•
집합의 삽입과 조회는 평균적으로
공간 복잡도
•
집합에 저장되는 문자의 수는 최대 알파벳의 종류 수()입니다. 가능한 문자 집합 크기 에 비례하여 공간을 사용하므로 로 표현하는 것이 더 일반적이다.
•
영어 소문자만 포함하면 로 간주할 수 있습니다.
예제3 - 특정 조건을 만족하는 숫자 찾기
배열에서 x + 1과 x - 1모두 포함되지 않은 숫자를 찾으세요.
nums = [1, 3, 5, 2, 4, 8]
# 결과: [8]
Python
복사
풀이: 집합(set)과 조건문 활용
def findNumbers(nums):
nums = set(nums) # 중복 제거 및 빠른 조회
result = []
for num in nums:
if (num + 1 not in nums) and (num - 1 not in nums):
result.append(num)
return result
Python
복사
동작 원리
1.
배열을 집합으로 변환하여 중복을 제거하고 존재 여부 확인을 효율적으로 수행
2.
각 숫자에 대해 (num + 1)과 (num - 1)이 없는지 확인
3.
조건을 만족하는 숫자를 결과 리스트에 추가
시간 복잡도
•
배열을 집합으로 변환:
•
집합을 순회하며 조건 확인:
•
전체 시간 복잡도:
공간 복잡도
•
집합에 배열의 모든 요소를 저장하므로
마무리
1.
해시 테이블과 집합은 요소의 존재 여부를 빠르게 확인
2.
시간 복잡도 최적화: 배열 탐색: → 해시와 집합으로 로 개선
3.
활용 사례
•
특정 합을 이루는 숫자 쌍 찾기
•
중복된 첫 번째 문자 찾기
•
특정 조건을 만족하는 숫자 찾기
Related Posts
Search
