📘📗📙 해시 (완주하지 못한 선수 ~ 베스트앨범)

프로그래머스

• 본 카테고리에서는 프로그래머스에서 제공되는 고득점 Kit 문제들을 다뤄볼까 합니다.
• 프로그래머스 환경은 기업이나 자격증 관련해서도 코딩 테스트에 자주 사용되기 때문에 익혀두시면 적응하기 편하실 것 같습니다.
• 실려있는 주제 순서대로 풀어갈 예정이며, 먼저 해시 관련 문제들을 살펴봅시다.

 

해시는 뭐죠?

• 해시는 데이터 저장, 검색 및 관리를 위한 기술로 key-value 쌍을 사용하여 데이터를 효율적으로 저장합니다.
• 해시는 해시 함수를 이용하여 key를 고유한 index(hash code)로 변환하고 이를 통해 데이터를 해시 테이블에 저장합니다.
• Python에서는 해시 테이블을 기반으로 하는 dictionary와 set을 제공합니다.

1. 딕셔너리(Dictionary): Python에서 key를 활용하여 value값을 찾아낼 때 사용되는 구조입니다.
2. 집합(Set): 고유한 요소들의 집합을 나타내는 해시 테이블 기반 자료 구조입니다. 기본적으로 딕셔너리의 key만을 이용하는 특별한 경우로 볼 수 있습니다.

• 해시를 사용하는 주요 이점은 평균적으로 O(1)의 시간 복잡도로 데이터 접근과 수정이 가능하다는 것입니다.

 

 Level 1 : 완주하지 못한 선수 

• 참여자 명단에는 있지만, 완주자 명단에는 없는 선수의 이름을 출력하는 문제입니다.
• 간단해 보이지만, 참여자 명단에 중복된 이름의 선수들도 생각해야하기에 쉽게 풀리지 않을 수 있습니다.
• 딕셔너리 관점에서 생각을 해보면 get() 함수를 활용해볼 수 있겠습니다.
• get() 함수는 첫 번째 인자로 key를 받고, 선택적으로 두 번째 인자를 넣게 되면 만약 해당 key 값이 있을 경우 value를, 없을 경우에는 두 번째 인자 값을 반환하게 됩니다.
• 이를 활용해 딕셔너리를 초기화해준 뒤, 완주자들을 가감하게 되면 count가 남아있는 선수가 완주하지 못한 선수가 됩니다. 코드를 확인해보시면 이해가 되실 겁니다.

def solution(participant, completion):
    count = {}

    for part in participant:
        count[part] = count.get(part, 0) + 1

    for comp in completion:
        count[comp] -= 1

    for part in participant:
        if count[part] > 0:
            return part

 

 Level 1 : 폰켓몬 

• 고를 수 있는 폰켓몬의 최대 종류 수를 반환해야 하는 문제입니다.
• 우선 종류 번호에 중복이 있기 때문에 set()을 이용하여 중복을 제거했습니다.
• 고를 수 있는 폰켓몬의 최대 종류 수가 총 폰켓몬 수의 절반을 넘기면 안되기 때문에, 이 절반과 중복을 제거한 폰켓몬 종류의 수를 비교하여 더 적은 수를 반환하면 되겠습니다. 코드로 확인해보시죠!

def solution(nums):
    answer = set(nums)
    return min(len(answer), len(nums) // 2)

 

 Level 2 : 전화번호 목록 

• 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지를 확인하는 문제입니다.
• 이 문제에서는 딕셔너리와 Set을 사용하여 각 전화번호를 더 빠르게 접근하고 비교할 수 있도록 했습니다.
• 각 전화번호의 길이를 Set으로 저장한 후, 각 전화번호에 대해 가능한 모든 접두어의 길이에서만 해시맵을 통해 검색하게 하였습니다.
• 만약에 현재 전화번호의 앞부분이 해시맵에 저장되어 있다면, 접두어가 전화번호부에 있다는 것을 의미합니다. 따라서 False를 반환하게 됩니다.

def solution(phone_book):
    hash_map = {}
    lengths = set()

    for phone_number in phone_book:
        hash_map[phone_number] = 0
        lengths.add(len(phone_number))

    for phone_number in phone_book:
        for length in lengths:
            if length < len(phone_number):
                if phone_number[:length] in hash_map:
                    return False
    return True

 

 Level 2 : 의상 

• 의상들이 배열로 주어질 때, 서로 다른 패션의 조합 수를 반환해주는 문제입니다.
• '완주하지 못한 선수' 문제에서 사용된 get() 함수를 다시 사용할 차례입니다! get() 함수와 딕셔너리 구조를 이용하여 옷 종류별로 개수를 계산합니다.
• 각 옷의 종류별로 옷을 입는 경우와 입지 않는 경우를 고려해서 경우의 수를 계산해줍니다.
• 마지막으로 모든 옷을 입을 수는 없기에 1가지 경우를 제외한 뒤, 조합의 수를 반환해줍니다.

def solution(clothes):
    clothes_dict = {}

    for _, category in clothes:
        clothes_dict[category] = clothes_dict.get(category, 0) + 1

    answer = 1
    
    for count in clothes_dict.values():
        answer *= (count + 1)
    
    return answer - 1

 

 Level 3 : 베스트앨범 

• 조금 난이도가 있습니다. 수록 조건이 3가지가 있기 때문에 이를 충족시키면서 베스트앨범에 노래를 수록하는 문제입니다.
• 첫 번째 조건을 만족시키기 위해 먼저 total_play라는 딕셔너리를 생성하고 get() 함수를 통해 재생 수를 누적시켰습니다. 이 딕셔너리는 장르의 총 재생 순위를 매기는 역할을 합니다.
• 다음으로는 장르별로 노래의 재생 수와 해당 고유 번호를 저장해주는 play_list_by_genre 딕셔너리를 추가적으로 생성하였습니다.
• 마지막 조건을 충족시키기 위해 sorted()에 lambda 식을 추가해 play_list_by_genre를 정렬해주었습니다.

def solution(genres, plays):
    answer = []
    total_play = {}
    play_list_by_genre = {}

    for idx, (genre, play) in enumerate(zip(genres, plays)):
        total_play[genre] = total_play.get(genre, 0) + play
        play_list_by_genre[genre] = play_list_by_genre.get(genre, []) + [(play, idx)]

    sorted_genre = sorted(total_play, key=lambda x: total_play[x], reverse=True)

    for genre in sorted_genre:
        play_list = sorted(play_list_by_genre[genre], key=lambda x: (-x[0], x[1]))
        for play in play_list[:2]:
            answer.append(play[1])

    return play_list_by_genre