Hash

블록체인, 암호화폐 기술에 항상 등장하는 것 중 하나가 해쉬함수이다. 

해쉬함수란 간단히 말하면 어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수를 이야기한다. 

 

특징. 

- 어떤 길이의 데이터도 입력으로 사용될 수 있다. 

- 결과는 정해진 길이로 나온다.

- 계산 시간이 합리적으로 추정 가능해야한다.

- 입력 길이에 제한이 없기 때문에 최소한 입력 길이에 선형적으로 비례하는 특성은 있어야한다. 

 

- 결과값이 중복될 일은 거의 없다.

- 입력값을 알 수 없다.

- 결과값을 알려주고 입력값을 찾을 수 있는 특벽한 공식이 없다. 

 

나는 좀 더 자세한 설명은. www.youtube.com/watch?v=Vi0hauJemxA ( 내 youtube 채널 아님 )에서 설명을 들었다. 

 

소스 예제는 (programmers.co.kr/learn/challenges) 에서 내가 직접 해쉬문제를 풀어보았다. 

프로그래머스 -> 코딩테스트 연습 -> 해쉬

 

1번. 완주하지 못한 선수 

# 12/28
# Hash_1
import nltk
import collections

participant = ["mislav", "stanko", "mislav", "ana"]
completion = ["stanko", "ana", "mislav"]


# 
def solution_2(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    answer.items()  # key - value 둘 다 반환
    answer.keys()   #
    answer.values()     #
    return list(answer.keys())[0]


# 
def solution_1(participant, completion):

    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[i+1]


# 
def solution_3(participant, completion):
    temp = 0
    dic = {}
    # tuple = set()
    # print(tuple)
    # exit(-1)
    # DB dic 의 형식 (key-value) 기본
    # ["mislav" : 3123.. , "stanko": -576... , "mislav": 3123... , "ana": 4185...]
    for part in participant:
        dic[hash(part)] = [part]
        print(hash(part))
        temp += int(hash(part))

    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer


# print(solution_1(participant, completion))
# collection_example()
print(solution_2(participant, completion))
# solution_3(participant, completion)

 

2번. 전화번호 목록 

# Hash_2

phone_book = ["123", "4567", "789", "7819", "12", "34"]


# 
def solution(phone_book):
    list = sorted(phone_book, key=len)          # key=len

    for i in range(len(phone_book)):
        # ['12', '34', '123', '789', '4567', '7819']
        # i:0  = 2
        # i:1  = 2
        # i:2  = 3
        l = len(list[i])
        for j in range(i+1, len(phone_book)):
            # print(list[i])      # 12
            # print(list[j])      # 34
            # print(list[j][:l])  # 34        # [:l]
            if list[i] == list[j][:l]:
                return False

    return True


# 해쉬
def solution_1(phone_book):
    answer = True
    hash_map = {}       # dictionary

    for phone_number in phone_book:  # number
        hash_map[phone_number] = 1      # 하나씩 꺼내서 dic 넣어줬어 value값은 1로 주면서
    # print(hash_map)

    #
    for phone_number in phone_book:     # p_n
        temp = ""           # 초기화
        for number in phone_number:     # n 숫자 하나씩 1, 2, 3, 4, 5, 6, 7, 8, 9
            print(number)
            temp += number  # 1 -> 12 -> 123
            # 비교
            if temp in hash_map and temp != phone_number:   #
                answer = False
    return answer


print(solution_1(phone_book))
# print(solution(phone_book))

 

3번. 위장 

# Hash_3.py
from collections import Counter
from functools import reduce


clothes_1 = [["yellow_hat", "headgear"],
             ["blue_sunglasses", "eyewear"],
             ["green_turban", "headgear"]]
clothes_2 = [["crow_mask", "face"],
             ["blue_sunglasses", "face"],
             ["smoky_makeup", "face"]]


def solution_1(clothes):
    answer = 1
    dic = {}

    # {("headgear" : [ yellow_hat, green_turban] ), (eyewear: [blue_sunglasses])}
    for name, cloth in clothes:
        if cloth in dic.keys():
            dic[cloth].append(name)
        else:
            dic[cloth] = [name]

    for val in dic.values():
        print(len(val))
        answer *= (len(val) + 1)

    print(answer - 1)


def solution_2(clothes):
    cnt = Counter([kind for name, kind in clothes])
    print(cnt)
    # reduce (함수, 몇번 호출 할 것인지, 초깃 값)
    answer = reduce(lambda x, y: x * (y + 1), cnt.values(), 1)
    # x = 1 : y = cnt.values(1)
    # x = 3 : y = cnt.values(2)
    # return 6
    return answer - 1
    # return reduce(lambda x, y: x*y, [a+1 for a in collections.Counter([x[1] for x in c]).values()])-1

# solution_1(clothes_1)
solution_2(clothes_1)

 

4번. 베스트 앨범

# Hash_4.py
genres = ["classic", "pop", "classic", "classic", "pop", "comma"]
plays = [500, 2500, 150, 800, 600, 2000]


def solution_1(genres, plays):
    answer = []     # 정답 return 값을 넣어줄 arr
    dic = {}        # dictionary
    total_sum = {}  # total_sum 을 저장 할 변수
    i = 0           # plays가 몇번 째에 들어가있는지 확인해주는 변수

    for gener, play in zip(genres, plays):  # 값을 묶어서 반환 순서쌍이 같을 때 자주 사용
        if gener in dic.keys():
            dic[gener].append((play, i))
        else:
            dic[gener] = [(play, i)]
        i += 1
    # print(dic)

    for gener in dic.keys():
        # print(dic[gener])  # [(500, 0), (150, 2), (800, 3)]   # 1차원 배열인데, 그 값이 튜플인 경우
        # key 배열 중에서 몇번째에 들어가 있는지 알려주는 것
        dic[gener].sort(key=lambda k: k[0], reverse=True)  # k = (500, 0) , k[0]을 사용하겠다.

        sum = 0
        for value in dic[gener]:
            sum += value[0]
        total_sum[gener] = sum

    print(total_sum)
    print(total_sum.items())    # dict_items([('classic', 1450), ('pop', 3100), ('comma', 2000)])
    exit(-1)                    # album_list = sorted(dict_items, reverse=True)
    # sort = 자기자신을 비교하고 값을 넣음, sorted return값이 있는 sort임
    total = sorted(total_sum.items(), key=lambda k: k[1], reverse=True)

    print(total)

    for gener, _ in total:
        if len(dic[gener]) > 1:  # plays 2개 이상일 때
            answer.append(dic[gener][0][1])
            answer.append(dic[gener][1][1])
        else:                   # # plays 1개 일 때
            answer.append(dic[gener][0][1])

    return answer


# solution_1(genres, plays)


def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1], e[2]])

    # d['classic'] = [plays, i]
    # sort ? x 관한 것을 sort  How? 정렬
    # d.keys() = classic, pop   x = 0 <- d.keys() 하나씩 (초기값), y => d['classic'] -> plays로 더 해주겠다.
    genreSort = sorted(list(d.keys()), key=lambda x: sum(map(lambda y: y[0], d[x])), reverse=True)
    print(genreSort)    # ['pop', 'comma', 'classic']

    # d['classic'] = [plays, i]
    for g in genreSort:  # 'pop' -> 'comma' -> 'classic'
        # dic[gener].sort(key=lambda k: k[0], reverse=True)
        temp = [e[1] for e in sorted(d[g], key=lambda x: (x[0], -x[1]), reverse=True)]
        answer += temp[:min(len(temp), 2)]
    return answer


solution(genres, plays)