[알고리즘, Python] 프로그래머스 고득점 Kit - Hash

해시 함수를 사용하여 키를 해시값을 매핑하고, 이 해시값을 주소 삼아 데이터의 값을 키와 함께 저장하는 자료구조

 

해시를 사용해야할 때

1. 리스트를 쓸 수 없을 때 사용: 인덱스 값을 숫자가 아닌 다른 값(문자열, 튜플)을 사용할 때
2. 빠른 접근/탐색이 필요할 때: 딕셔너리 함수의 시간 복잡도는 대부분 O(1)
3. 집계가 필요할 때 ex. 원소 개수 셀 때 = collections 모듈의 Counter 클래스 사용

⇒ 딕셔너리 사용해서 구현

 

딕셔너리 vs  리스트

= 원소를 넣거나(Insert) 삭제(Delete), 찾는(Search) 일이 많을 때는 딕셔너리를 사용하는 것이 효율적

 

용어 정리

• 해시(Hash): 임의 값을 고정 길이로 변환
• 해시 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해시 값(Hash Value) 또는 해시 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
• 슬롯(Slot): 한 개 데이터를 저장할 수 있는 공간

 

1. 해시 테이블을 위한 데이터 저장공간 만들기

data = list([0 for i in range(8)]) # [0, 0, 0, 0, 0, 0, 0, 0]

 

2. 내장 함수 hash()로 해시키 만들기

hash('Dave') #-1234590
hash('Dave') % 8 #2

 

3. 해시 함수 만들기

# 임의로 8개의 해싱함수 만들어보기
def hash_function(string):
    return hash(string) % 8

 

4. 해시 함수를 사용해서 데이터 (Value) 저장하기

data[hash_function('Dave')] = '000-1111-2222'
data[hash_function('David')] = '000-2222-3333'

 

5. 해시 함수를 사용해서 데이터 (Value) 읽어오기

data[hash_function('Dave')] # '000-1111-2222'

 

 

 

딕셔너리 함수

• in: 딕셔너리에 키가 있는지 확인

students = {'kim': 17, 'lee': 15, 'park': 18}

if 'kim' in students:
	print('kim is in students')
else:
	print('kim is not in students')
    
if 'son' in students:
	print('son is in students')
else:
	print('son is not in students')

• keys(): 딕셔너리의 키 뽑기

print(students.keys())

for student in students.keys():
	print(student)
    
>> dict_keys(['kim', 'lee', 'park'])

>> kim
>> lee
>> park

• values(): 딕셔너리의 값 뽑기

print(students.values())

for age in students.values():
	print(age)
    
>> dict_values([17, 15, 18])

>> 17
>> 15
>> 18

• items(): 딕셔너리 키, 값 합쳐서 뽑기

print(students.items())

for student_info in students.items():
	print(student_info)
    
>> dict_items([('kim', 17), ('lee', 15), ('park', 18)])

>> ('kim', 17)
>> ('lee', 15)
>> ('park', 18)

• get(): 딕셔너리 키로 값 얻기

print(students.get('kim'))
>> 17

orint(students.get('son'))
>> None

• del: 딕셔너리에서 키, 값 한쌍 지우기

del students['kim']
print(students)
>> {'lee': 15, 'park': 18}

del students['son']
>> error 발생

• clear(): 딕셔너리에서 키, 값 모두 지우기

students.clear()
print(students)
>> ""

 

---

프로그래머스 문제

완주하지 못한 선수 (Lv.1)

import collections

def solution(participant, completion):
    dict = collections.Counter(participant) - collections.Counter(completion)
    
    return_value = 0
    for key, value in dict.items():  # value 값으로 key 찾기
        if value == 1:
            return_value = key
            
    return return_value

 

 

폰켓몬 (Lv.1)

def solution(nums):
    n = int(len(nums)/2)
    count = len(set(nums)) # 리스트 중복 제거
    
    if n > count: # count가 n보다 작을 경우 둘이 대치
        n, count = count, n
    
    return(n)

 

 

전화번호 목록 (Lv.2)

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return_v = False
            break
        else: return_v = True
        
    return return_v

 

의상 (Lv.2)

def solution(clothes):
    # 1. 옷을 종류별로 구분하기
    hash_map = {}
    for clothe, type in clothes:
        hash_map[type] = hash_map.get(type, 0) + 1
        
    # 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
    answer = 1
    for type in hash_map:   
        answer *= (hash_map[type] + 1)
    
    # 3. 아무종류의 옷도 입지 않는 경우 제외하기
    return answer - 1

베스트 앨범 (Lv.3)

def solution(genres, plays):
    answer = []
    temp = []
    total_genre_d = {}

    temp = [[genres[i], plays[i], i] for i in range(len(genres))]   # [장르, 재생횟수, 고유 번호] 리스트
    temp = sorted(temp, key=lambda x: (x[0], -x[1], x[2]))  # 많이 재생될수록, 같다면 고유번호가 낮을수록

    for g in temp:  # {장르 : 총 재생횟수} 딕셔너리 생성
        if g[0] not in total_genre_d:
            total_genre_d[g[0]] = g[1]
        else:
            total_genre_d[g[0]] += g[1]
    
    total_genre_d = sorted(total_genre_d.items(), key = lambda x: -x[1])    # 재생횟수가 많은 순서로 장르 정렬
    
    for i in total_genre_d: # 같은 장르 내에서는 최대 2곡까지 조건대로 수록
        count = 0
        for j in temp:
            if i[0] == j[0]:
                count += 1
                if count > 2:
                    break
                else:
                    answer.append(j[2])

    return answer