Hash Table – Nextra

이 저작물은 개발남노씨 - 코딩테스트 [ ALL IN ONE ] (opens in a new tab)을 참고하여 작성되었습니다.

정의

Hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. hash function $h$에 key값을 입력으로 넣어 얻은 해시값 $h(k)$를 위치로 지정하여 key- value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간복잡도는 모두 $O(1)$입니다.

Collision

collision이란 서로 다른 key의 해시값이 똑같을 때를 말합니다. 즉, 중복되는 key는 없지만 해시값은 중복이 된 경우를 말합니다.

Dictionary

Python에서 Hash Table을 구현한 방법을 Dictionary 자료형이라고 한다.

시간 복잡도

추가, 삭제, 검색 모두 Big-O(n)의 시간복잡도를 가집니다.
아래의 코드는 dictionary에서 검색을 하는 기본적인 코드이고 이는 Big-O(n)의 시간 복잡도를 가진다.

hash = {
  "math" : 97,
  "eng" : 100,
  "kor" : 95
}
 
if "music" in hash : 
  print(True)
else : 
  print(False)

문제

Two Sum

two-sum (opens in a new tab)

two sum 문제를 dictionary를 활용해서 시간 복잡도 Big-O(n)으로 풀어보자.

내 풀이

기존 완전 탐색의 3000+ms 에서 80ms로 runtime이 줄어들었다.
어려웠던 점은, 두 개의 다른 인덱스에서 같은 값을 가지는 경우 인덱스를 구분해야 한다는 점이 어려웠다.
Two Pointer를 사용하면 쉽게 해결이 되지만 시간 Big O(n^2)이 되어버린다는 점에서 의미가 없었다.

class Solution:
  def twoSum(self, numbers: list[int], target: int) -> list[int]:
    dict1 = {}
    idx = 0
    for n in numbers :
      if n in dict1 :
        dict1[n] = dict1[n] + [idx]
      else : 
        dict1[n] = [idx]
      idx += 1
 
    idx = 0
    for n in numbers :
      need = target - n
      if need in dict1 :
        if idx == dict1[need][0] :
          try :
            first = dict1[need[0]]
            second = dict1[need][1] 
            return [first, second]
          except : 
            pass
        else : 
          return [idx, dict1[need][0]]
      idx += 1
    return []

Longest Consecutive Sequence

Link (opens in a new tab)

내 풀이

문제점 : 중복된 값이 들어올 경우 8번 라인에서 else로 넘어가버려 새로운 key를 생성하게 되고 이러면 cnt가 이어지지 않는다. 그래서 이후에 중복된

elif dict1[cnt][-1] == n :
  continue

를 추가해서 중복된 값일 경우에는 무시하도록 했다. 그랬더니 2. 문제점 : 시간초과 에러가 발생한다. 정렬, 즉 O(n log n)으로도 문제를 풀면 안되나보다. 그래서 문제 조건을 다시 읽어보니

You must write an algorithm that runs in O(n) time.

강의와는 다르게 O(n^5)가 제약 조건이 아니었다. 즉, "정렬하지 마라"라는 소리다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
      nums.sort()
      dict1 = {}
      cnt = 0
      for n in nums : 
        try : 
          if dict1[cnt][-1] == n - 1 :
            dict1[cnt] = dict1[cnt] + [n]
          else :
            cnt += 1
            dict1[cnt] = [n]
        except : 
          dict1[cnt] = [n]
 
      values1 = dict1.values()
      cnt = 0
      for v in values1 :
        if(len(v) > cnt) :
          cnt = len(v) 
          
      return cnt

강사님 풀이

다음 수를 찾기 위해서 반드시 반복이 요구되게 된다. 단지 모든 수에 대해서 반복하게 되면 이는 완전 탐색으로 시간 복잡도가 O(n^2)가 된다.
그래서 생각의 시작은 특정한 조건에서만 반복할 수는 없을까? 였다. 여기서 특정한 조건이란, 처음 순서가 시작할 때만 반복을 하면 된다는 것이었고 hash table에 해당 수의 이전에 해당하는 수가 없다면(즉 순열의 첫 부분이라면) 다음에 해당하는 수가 나오지 않을 때까지 반복을 해주고 매번 max와 비교를 해줘서 더 큰 값을 max로 지정해준다. 그리고 max를 return해주면 끝이 나는 것이다.
결국 아래의 코드는 2 * n, 즉, O(n)의 시간 복잡도를 가지게 된다.

class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    hash = {}
    longest = 0
    for n in nums : 
      hash[n] = True
    
    for n in nums : 
      # 순열의 첫 부분인지 검증
      if n-1 not in hash : 
        cnt = 1
        target = n + 1
        # 여기에서 hash 대신 nums가 들어가게 되면 시간 복잡도가 O(n^2)가 된다.
        while target in hash :
          target += 1
          cnt += 1
          
        longest = max(longest, cnt)
        
    return longest

set

Hash Set을 사용해서

for n in nums : 
  hash[n] = True

이 부분을

hash = set(nums)

또는

hash = {x: x + 1 for x in nums}

와 같은 형식으로 저장할 수 있다.

큐와 스택 트리