[python] 해시

해시란?

해시(hash)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 자료구조로, 번호로 주어진 index가 아닌 문자열 같은 다른 것으로 접근할 수 있다. 즉, dictionary, json 같은 자료형이다.
이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다.

Dictionary

Key-value 쌍들의 집합으로 이루어져 있다.
{'key1':value1, 'key2':value2, 'key3':value3}

딕셔너리와 리스트의 시간 복잡도 차이
딕셔너리의 시간 복잡도는 대부분 O(1)을 갖는데, 리스트와 시간복잡도를 비교해보면 아래와 같다.

Operation Dictionary List
Get Item O(1) O(1)
Insert Item O(1) O(1) ~ O(N)
Update Item O(1) O(1)
Delete Item O(1) O(1) ~ O(N)
Search Item O(1) O(N)
List에 비해 Dictionary가 매우 빠른 시간복잡도를 갖는다.

즉 , 원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용하는 것이 좋다.

삽입

dic_name['key_name'] = value

삭제

del dic_name['key_name']

키 값 뽑아내기

dic_name.keys()
### 결과는 아래 형식
dict_keys(['naver', 'Daum KAKAO', 'daeshin'])

list(dic_name.keys())
['naver', 'Daum KAKAO', 'daeshin']

value 값 뽑아내기

value_list = list(dic_name.values())

Json

문제 1 - 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

def solution(participant, completion):
    result = {}
    for p in participant:
        if p in result:
            result[p] += 1
        else:
            result[p] = 1
    for c in completion:
        result[c] -= 1
        if result[c] == 0:
            del result[c]
    answer = list(result.keys())[0]
    return answer

counter 객체를 이용해보자!

from collections import Counter```
Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})

위 카운터 객체는 덧셈 뺄셈이 가능함.

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

문제 2 - 폰켓몬

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

from collections import Counter

def solution(nums):
    tmp = Counter(nums)
    answer = len(list(tmp.keys()))
    if answer > len(nums)//2:
        answer = len(nums)//2
    return answer

문제 3 - 전화번호

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

def solution(phone_book):
    phone_book = sorted(phone_book)
    for i, j in zip(phone_book, phone_book[1:]):
        if j.startswith(i):
            return False
    return True

문제 4 - 위장

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

입출력 예
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] -> 5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] -> 3

def solution(clothes):
    dic = {}
    answer = 1
    for cloth in clothes:
        tmp_key = cloth[1]
        if tmp_key in dic:
            dic[tmp_key] += 1
        else:
            dic[tmp_key] = 1
    for i in list(dic.values()):
        answer = answer * (i+1)
    answer -= 1
    return answer

문제 5 - 베스트 앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

def solution(genres, plays):
    answer = []
    total={} 
    gen_dic={} 
    
    for i in range(len(genres)):
        genre = genres[i]
        play = plays[i]
        if genres[i] in total.keys():
            total[genres[i]]+=plays[i]
            gen_dic[genres[i]].append((plays[i],i))
        else:
            total[genres[i]]=plays[i]
            gen_dic[genre]=[(play,i)]

    total = sorted(total.items(), key=lambda x: x[1], reverse=True)
    
    for key in total:
        playlist = gen_dic[key[0]]
        playlist = sorted(playlist, key=lambda x: x[0], reverse=True)
        for i in range(len(playlist)):
            if i==2:
                break
            answer.append(playlist[i][1])
    return answer