[Python 파이썬] 해시 (Hash) 해싱 (Hashing) 알고리즘 예제로 알아보기

 

 

파이썬 코딩테스트에 출제 빈도가 높은 파이썬 '해시' 에 대해 알아보기

 

 

 

해시 / 해싱 / Hash / Hashing 

 

- 데이터를 빠르게 넣거나 or 가져올 때 사용하는 기법 

  : 해시로 풀어야하는 코딩 테스트의 경우 *** (아래 예제 有) -> 리스트로 풀게되면 효율성 테스트 실패 ! 

- 최솟값 or 최댓값을 찾을 때 (전체 자료를 모두 검색하는 경우) 효율이 떨어짐 

- 파이썬의 딕셔너리가 해시 테이블로 구현되어 있음

 

 

 

해시관련 알고리즘을 접한 후에, 해시의 유용함에 대해 알게 되었습니다. 먼저 프로그래머스 level2 의 해시 대표문제 '전화번호 목록' 을 보겠습니다. 먼저 해시를 사용하지않은 코드, 그리고 해시를 사용한 코드의 실행 시간을 비교해 보겠습니다. 

 

 

파이썬 실행시간 계산 / 측정 방법

https://codingpractices.tistory.com/64

[Python] 함수 실행 경과 시간 계산하기 time() time_process()

 

 

---

 

 

해시 문제 : 프로그래머스 Level 2  전화번호 목록

 

• 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_bookreturn

["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

---

 

해시를 이용하지않은 풀이 

- 모든 케이스를 통과하나 효율성테스트 실패합니다. 

def solution(phone_book):
    answer = True
  
    for i in phone_book:
        temp=''
        for j in i:
            temp += j
            if temp in phone_book and temp != i:
                answer = False
  
    return answer

      

 

 

 

해시를 사용한 정석 풀이

def solution(phone_book):
  answer = True
  hash = {}
  
  for i in phone_book:    # 모든 요소를 (전화번호) { '전화번호' : 1} 이렇게 담는다 
    hash[i] = 1

  for i in phone_book:
    temp=''
    for j in i:
      temp += j
      if temp in hash and temp != i:           #담아놓은 hash에서 요소 찾기 
        answer = False
  
  print(answer)
  

solution(["119", "97674223", "1195524421"])
solution(["123","456","789"])

      

 

 

 

이렇게 해시 Hash를 사용하게되면 효율성도 통과하게 됩니다. 바뀐 부분은 hash 로 해당 요소들을 쭉 담아서 해당 요소가 있는지 확인하는 부분에 hash 를 썼는데 이 부분에서 해시의 속도가 빠른 듯 합니다. 

Hash 관련 알고리즘을 풀 때마다 계속 분석해보면서 어떤 장단점이 있는지 직접 기록을 해봐야겠습니다 :D