해시의 원리를 이해하고 문제에서 요구하는 해시 함수를 구현할 수 있습니다.
3편은 해시 몸풀기 문제 2개입니다.
총 3편으로 준비했습니다.
1. 해시의 개념
2. 해시 함수와 충돌 처리
3. 해시 몸풀기 문제
문제 01 두 개의 수로 특정값 만들기 ⭐️
- 저자 권장 시간: 30분
- 권장 시간 복잡조: O(N+K)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/18.py
n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False를 반환하는 solution( ) 함수를 작성하세요.
제약 조건
- n은 2 이상 10,000 이하의 자연수입니다.
- arr의 각 원소는 1 이상 10,000 이하의 자연수입니다.
- arr의 원소 중 중복되는 원소는 없습니다.
- target은 1 이상 20,000 이하의 자연수입니다.
입출력의 예
문제 분석하고 풀기
arr에서 특정 원소 두 개를 뽑아 두 수의 합이 target과 같을 수 있는지 확인하는 문제입니다. 첫 번째 입출력을 보겠습니다. arr이 [1, 2, 3, 4, 8]이고 target이 6입니다. 여기서는 두 가지 방법을 알아볼 겁니다. 첫 번째 방법은 무작정 가능한 모든 경우의 합을 확인하고, 두 수의 합이 되는지 확인하는 방법입니다. 두 번째 방법은 해시를 활용하는 방법입니다.
무작정 더하며 찾기
가장 간단한 방법은 각 원소에 대해 자신을 제외한 나머지 원소를 전부 더하면서 두 수의 합이 6인 경우를 찾는 겁니다. 이렇게 하면 정답은 당연히 나오겠지만 시간 복잡도는 O(N2)이므로 데이터가 최대 10,000개까지 들어오는 것을 가정하면 대략 1억 번의 연산이 수행될 수 있으므로 효율이 떨어집니다. 뭔가 개선이 필요합니다.
해시를 활용해 찾기
어떻게 개선할 수 있을까요? 코드를 구현하기 전에 별 아이디어가 떠오르지 않다면 직접 이 문제를 풀어보는 것도 방법입니다. 만약 여러분이 이 문제를 직접 푼다면 하나의 숫자를 고른 다음 그 숫자를 더했을 때 target이 되는 수가 arr에 있는지 확인해볼 겁니다. 그러니 다음과 같은 관점으로 문제에 접근할 수도 있을 겁니다.
“arr에서 임의의 원소 x에 대해 x + k = target이 되는 원소 k가 arr에 있는지 확인하기”
여기서 핵심은 k를 확인하는 동작의 효율입니다. 문제에서는 x, k는 모두 arr의 원소라고 했으므로 원소의 유무를 표시할 수 있는 해시 테이블 hash_table을 마련해 활용하면 O(1) 안에 찾을 수 있습니다. 그림으로 표현하면 다음과 같습니다.
왼쪽이 arr, 오른쪽이 arr을 보고 각 원소의 유무를 표현한 해시 테이블입니다. 해시 테이블의 크기는 arr의 원소 중 가장 큰 원소의 값 8과 같습니다. 1, 2, 3, 4, 8에 대해서는 1을, 나머지 수에 대해서는 0을 매치했습니다. 이렇게 해시 테이블을 준비하고 각 원소에 대해 hash_table(target – 원소)가 1이면 합을 통해 target을 만들 수 있는 두 수가 arr에 있다고 봐도 됩니다.
다음 코드는 계수 정렬(Counting Sort) 알고리즘을 사용해 배열 arr에서 문제에서 요구한 target을 찾는 함수를 구현한 겁니다. 계수 정렬 알고리즘은 입력 배열을 순회하며 각 원소의 등장 횟수를 세는 작업을 수행합니다. 코드를 보면 arr의 각 원소를 순회하면서 현재 원소의 값이 k 이하일 때 순회 대상 원소를 인덱스로 하는 해시 테이블의 값을 1로 설정합니다.
※ 계수 정렬은 ‘13장 정렬’에서 자세히 설명하므로 궁금하다면 잠깐 넘어가 공부하고 오기 바랍니다.
def count_sort(arr, k):
# ➊ 해시 테이블 생성 및 초기화
hashtable = [0] * (k + 1)
for num in arr:
# ➋ 현재 원소의 값이 k 이하인 때에만 처리
if num <= k:
# ➌ 현재 원소의 값을 인덱스로 해 해당 인덱스의 해시 테이블 값을 1로 설정
hashtable[num] = 1
return hashtable
def solution(arr, target):
hashtable = count_sort(arr, target)
for num in arr:
complement = target - num
# ➍ target에서 현재 원소를 뺀 값이 해시 테이블에 있는지 확인
if (
complement != num
and complement >= 0
and complement <= target
and hashtable[complement] == 1
):
return True
return False
solution( ) 함수는 ❶ count_sort( ) 함수를 호출해 해시 테이블을 생성한 후 배열 arr을 순회하며 다음 작업을 수행합니다. ➋ 현재 원소 num에 대해서 target – num을 계산해 그 값이 해시 테이블에 있는지 확인합니다. 이때 target에서 현재 원소를 뺀 값이 현재 원소와 다르고, 0 이상이며 target 이하인지 확인하고, 해시 테이블의 값이 1인지 확인합니다. 이 조건을 만족하면 True를 반환하고 모든 원소에 대해 검사를 완료한 후에도 찾지 못하면 False를 반환합니다.
시간 복잡도 분석하기
N은 arr의 길이이고, K는 target의 길이입니다. count_sort( ) 함수의 시간 복잡도는 해시 테이블을 초기화할 때 시간 복잡도는 O(K), 배열 arr을 순회할 때 시간 복잡도는 O(N)이므로 O(N +K)입니다. solution( ) 함수의 시간 복잡도는 count_sort( ) 함수를 호출하면서 arr을 O(N)으로 순회하므로 최종 시간 복잡도는 O(N + K)이 됩니다.
문제 02 문자열 해싱을 이용한 검색 함수 만들기 ⭐️⭐️
- 저자 권장 시간: 40분
- 권장 시간 복잡조: O(N+K)
- 출제: 저자 출제
- Github: https://github.com/dremdeveloper/codingtest_python/blob/main/solution/19.py
문자열 리스트 string_list와 쿼리 리스트 query_list가 있을 때 각 쿼리 리스트에 있는 문자열이 string_list의 문자열 리스트에 있는지 여부를 확인해야 합니다. 문자열이 있으면 True, 없으면 False가 됩니다. 각 문자열에 대해서 문자열의 존재 여부를 리스트 형태로 반환하는 solution( ) 함수를 작성해주세요.
제약 조건
- 입력 문자열은 영어 소문자로만 이루어져 있습니다.
- 문자열의 최대 길이는 106입니다.
- 해시 충돌은 없습니다.
- 아래와 같은 문자열 해싱 방법을 활용해서 해싱 함수를 구현하세요.
- 다음 식에서 p는 31, m은 1,000,000,007로 합니다.
- hash(s) = (s[0] + s[1]*p + s[2]*p2 …….. s[n-1]*pn-1) mod m
입출력의 예
문제 분석하고 풀기
문자열 해싱에 대한 개념은 앞서 자세히 설명했으므로 여기서 설명하지 않아도 될 것 같네요. 바로 문제를 풀어봅시다. string_list의 각 문자열들을 아스키코드값과 문자열 해싱으로 생성한 해시 값을 활용해서 해시에 저장합니다. 이후 query_list의 각 문자열들도 해싱한 후 해당 값이 해시에 있으면 True, 아니면 False를 반환합니다.
# ➊ polynomial hash를 구현한 부분
def polynomial_hash(str):
p = 31 # 소수
m = 1_000_000_007 # 버킷 크기
hash_value = 0
for char in str:
hash_value = (hash_value * p + ord(char)) % m
return hash_value
def solution(string_list, query_list):
# ➋ string_list의 각 문자열에 대해 다항 해시값을 계산
hash_list = [polynomial_hash(str) for str in string_list]
# ➌ query_list의 각 문자열이 string_list에 있는지 확인
result = [ ]
for query in query_list:
query_hash = polynomial_hash(query)
if query_hash in hash_list:
result.append(True)
else:
result.append(False)
return result
➊ 문자열 해싱을 구현한 부분입니다. 문자열 해싱을 하려면 각 문자의 아스키코드값이 필요합니다. ord( ) 함수는 특정 문자의 유니코드값을 반환하지만 예제에서는 영어 소문자만을 사용하므로 아스키코드값을 반환합니다. ➋ 각 string_list의 문자열들을 해싱하고 이를 기준으로 해시 테이블을 완성합니다. ➌ query_list의 각 문자열 해싱값이 해시 테이블에 있으면 True, 아니면 False를 result에 추가합니다.
시간 복잡도 분석하기
N은 string_list의 길이이고, K는 query_list의 길이입니다. polynomial_hash( ) 함수를 보면 충돌이 없다고 가정했으므로 시간 복잡도는 O(1)입니다. 다음으로 solution( ) 함수를 보면 string_list의 각 문자열에 대해 해시값을 계산하여 O(N), query_list의 각 문자열이 string_list에 있는지 확인하여 O(K)입니다. 따라서 최종 시간 복잡도는 O(N + K)입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
