해시는 Key-Value 쌍으로 데이터를 저장하는 자료구조이다. 해시 알고리즘에 대한 예를 정리해 보았다.

Step 1. 완주하지 못한 선수

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 리턴하는 알고리즘. 완주하지 못한 선수는 단 한 명으로, completion의 길이는 participant보다 1 짧으며, 참가자 중에는 동명이인이 있을 수 있다.

• 문제 링크

예시 1

def solution(participant, completion):
    for ele in completion:
        participant.remove(ele)
    return participant[0]

• participant에서 completion에 있는 사람들을 하나씩 뺀 것으로, 테스트 케이스에서 시간 초과한 코드이다.
• .remove를 통해 participant에서 ele라는 값 을 찾아서 제거해야 하기 때문에 속도가 느려지는 듯 하다.

예시 2

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for p, c in zip(participant, completion):
        if p != c:
            return p

• participant와 completion을 정렬 하고 순서가 맞지 않는 참가자를 리턴하는 코드이다. .sort로 정렬하는 과정은 속도에 큰 영향을 미치지 않는 것으로 보인다.

예시 3

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += hash(part)
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

• hash 함수를 사용한 경우이다. hash(value)는 value의 주소를 반환해 준다.
• 해시가 Key-Value 쌍으로 데이터를 저장하는 자료구조라는 특성을 활용한 예이다. temp에 참가자들의 주소를 더한 후에 완주자들의 주소를 빼서 완주하지 못한 사람의 주소만 남기도록 해 준다.
  
  

Step 2-1. 전화번호 목록

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 리턴한다. 예를 들어 전화번호 목록이 [“123”, “12345”]일 경우 “123”은 “12345”의 접두어이므로 false를 리턴한다.

• 문제 링크

예시 1

def solution(phone_book):
    for a in phone_book:
        for b in [ele for ele in phone_book if ele != a]:
            if len(b) >= len(a) and b[0:len(a)] == a: # 접두어이므로, 비교할 단어(b)의 길이가 더 길어야 함
                return False
    return True

• phone_book의 각 요소(a)와 자기 자신을 뺀 요소(b) 중 자기보다 큰 요소를 비교하여, a가 b의 접두어이면 False를 리턴하는 함수이다.

예시 2

def solution(phone_book):
    phone_book.sort()
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1): # 바로 다음 거랑만 비교
            return False
    return True

• phone_book을 정렬한 경우이다. 전화번호들이 string 형식으로 주어지므로, 한 단어가 다른 단어의 접두어일 경우 바로 다음 순서 로 정렬되는 것을 활용한 것이다. 접두어를 확인하는 것은 string.startswith 메소드를 이용하였다.
  
  

Step 2-2. 위장

스파이들은 매일 다른 조합의 옷을 입어야 한다. 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return하는 함수를 작성한다. clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있다. 같은 이름을 가진 의상은 존재하지 않으며, 스파이는 하루에 최소 한 개의 의상은 입는다.

• 문제 링크
• 예: [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
  • 1가지 옷만 입는 경우의 수 = 총 옷의 개수 = 3
  • 2가지 옷을 입는 경우의 수: 2
    • blue_sunglasses + yellow_hat
    • blue_sunglasses + green_turban
  • 따라서 답은 5

예시 1

from itertools import combinations

def solution(clothes):
    answer = 0
    cloth_dict = {}
    for c,t in clothes:
        if t in cloth_dict.keys(): # 이미 있는 종류면
            cloth_dict[t].append(c)
        else: # 새로운 종류면
            cloth_dict[t] = [c]
        answer += 1 # 1가지 옷을 입은 경우의 수

    for i in range(2, len(cloth_dict.keys()) + 1):
        for keys in combinations(cloth_dict.keys(), i): # 전체 종류 중 i개 고른 조합
            temp = 1
            for key in keys:
                temp *= len(cloth_dict[key])
            answer += temp
    return answer

• 1가지 옷을 입는 경우의 수는 총 옷의 개수
• 2가지 옷을 입는 경우의 수는 전체 종류 개수에서 2가지를 택하고, 2가지 종류에서 각 종류의 옷의 개수를 곱한 것이다.
• 이런 식으로 총 옷 종류 개수가 될 때까지 반복하여 계산하면 된다.
• 옷 카테고리 중 n개를 고른 조합을 뽑기 위해 itertools.combinations를 사용했다. 이 경우 시간 초과 에러가 났다.

예시 2

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t in clothes_type:
            clothes_type[t] += 1
        else:
            clothes_type[t] = 2

    cnt = 1
    for num in clothes_type.values():
        cnt *= num

    return cnt - 1

• 종류별로 옷 개수가 a,b,c,…라고 하면 [(a+1) * (b+1) * (c+1) * ...] - 1 이 답이 된다.
• 한 종류에서 옷이 3개라고 하면 입지 않는것, 첫 번째 종류, 두 번째 종류, 세 번째 종류 총 4개의 선택이 가능하고, 각 종류별로 곱하면 모든 경우의 수가 나오게 된다. 아무것도 입지 않는 경우는 제외해야 하므로 1을 빼야 한다.

이와 비슷하게 python 라이브러리를 사용하여 다음과 같이 짤 수도 있다.

from collections import Counter
from functools import reduce

def solution(clothes):    
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

• Counter는 종류별(kind) 개수를 반환해 주는 함수, reduce는 초기값(1)에 해당 배열의 원소들을 하나씩 계산해 주는 함수이다.
  
  

Step 3. 베스트앨범

베스트 앨범을 출시하려 함. 장르 별로 가장 많이 재생된 노래를 두 개씩 추출. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 추출. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 리턴하는 함수를 작성한다.

• 문제 링크
• 예: ["classic", "pop", "classic", "classic", "pop", "classic"], [800, 600, 600, 800, 2500, 2500]
  • classic, pop 장르의 재생 횟수 합은 각각 4700, 3100
  • classic 장르 먼저 2개 추출: 5,0번째 index
  • 다음으로 pop 장르 2개 추출: 4,1번째 index
  • 따라서 답은 [5,0,4,1]

예시 1

def solution(genres, plays):
    dic = {}
    for i in range(len(genres)):
        if genres[i] in dic.keys():
            dic[genres[i]]['items'].append([i, plays[i]])
            dic[genres[i]]['sum'] += plays[i]
        else: # 처음 오는 장르
            dic[genres[i]] = {}
            dic[genres[i]]['items'] = [[i, plays[i]]]
            dic[genres[i]]['sum'] = plays[i]
    print(dic)

    # 장르별로 정렬
    dic = sorted(dic.items(), key=(lambda x:x[1]['sum']), reverse=True)

    answer = []
    for g, item in dic:
        # 장르 안에서 조회수별로 정렬
        item['items'].sort(key=(lambda x:x[1]), reverse=True)
        for ele in item['items'][:2]:
            answer.append(ele[0])

    return answer

• dic의 형태는 다음과 같다. 장르별 합과 [인덱스, 재생 횟수]를 저장한다.

  {'classic': {'items': [[0, 800], [2, 600], [3, 800], [5, 2500]], 'sum': 4700},
  'pop': {'items': [[1, 600], [4, 2500]], 'sum': 3100}}
  

• 각 장르 안에서는 조회수별로 정렬하고, 상위 2개 인덱스를 추출한다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 추출해야 하는데, dic에 각 원소들을 담을 때 인덱스 순서대로 담으므로 answer에도 앞의 인덱스 노래가 먼저 담긴다. 따라서 이 코드에서 특별히 처리해 줄 필요는 없다.

---

출처: 프로그래머스 해시 문제