출처 : 프로그래머스

완주하지 못한 선수

참가자와 완주자 리스트가 있다.
참가자 수와 완주자 수는 딱 1만큼 차이가 난다.
완주자 리스트를 기반으로 참가자 가운데 누가 완주하지 못했는지 찾아내야 한다. (빨리!)
1. 완주자 리스트를 순회하며 딕셔너리를 만든다. 이때 완주자 이름당 카운트를 한다. ( 동명이인 존재 )
2. 이후 참가자 리스트를 순회하며 딕셔너리를 만든다. 이때 참가자 이름당 카운트를 한다. ( 동명이인 존재 )
3. 그래서 참가자/완주자 숫자가 다르다면 이놈이 완주하지 못한 놈이고, 참가자에는 있지만 완주자에 없다면 이놈도 완주하지 못한 놈이다.

# def solution(participant, completion):
    
#     for complete_id in completion:
#         participant.remove(complete_id)
#     answer = participant[0]
#     return answer

def completion_dic(completion):
    hash_dic = {}
    
    for completion_id in completion:
        if completion_id in hash_dic:
            hash_dic[completion_id] = hash_dic[completion_id] +1
        else:
            hash_dic[completion_id] = 1
    return hash_dic

def participant_dic(participant):
    hash_dic = {}
    
    for participant_id in participant:
        if participant_id in hash_dic:
            hash_dic[participant_id] = hash_dic[participant_id] +1
        else:
            hash_dic[participant_id] = 1
    return hash_dic

def solution(participant, completion):
    
    comp_dic = completion_dic(completion)
    part_dic = participant_dic(participant)
    
    for participant_id in participant:
        # no same name
        if participant_id not in comp_dic:
            answer = participant_id
        
        # yes same name
        else:
            if part_dic[participant_id] != comp_dic[participant_id]:
                answer = participant_id
        
    return answer

처음에는 틀릴줄 알았지만 list 로 접근.
시간 초과로 탈락.

값에 바로 접근하는 dict 특성상, 계산 복잡도는 O(1) ~ O(n) 이다.
반면에 list 는 O(n).

전화번호 목록에서 접두어 찾기

1. 폰 넘버들의 개수 혹은 여기서는 존재 유무만을 따지는 해쉬 맵을 만든다.
2. 모든 폰넘버 리스트에서 순회하며 접두어가 1번에서 생성한 해쉬 맵에 존재하는지 따진다.

# 접두어 dictionary
# 중요 아이디어 : 폰넘버가 해쉬맵에 존재하는지 여부를 1로 표현
def str_to_dic(dic, phone_num):

    dic[phone_num] = 1
    return 1

# given strings, comparing algo
def solution(phone_book):
    answer = True
    dic = {}
    for phone_num in phone_book:
        str_to_dic(dic, phone_num)
    
    # 폰넘버별로 가능한 모든 접두어 경우의 수를 해쉬 맵에서 찾는다
    for phone_num in phone_book:
        startswith = ''
        for char in phone_num[:-1]:
            startswith = startswith+char
            
            # 접두어 경우의 수 가운데 해쉬 맵에 존재한다면
            if startswith in dic:
                answer = False
    
    return answer

처음에 해쉬 맵을 사용하는 법을 잘 모르는것 같다.
자꾸 list적인 접근을 한다.

처음 접근했던 방법도 모든 접두어의 경우의 수를 구해서 해쉬 맵을 만들었다.
모든 접두어의 경우의 수를 만든다 -> 2중 포문. -> 계산 탈락

해쉬는 값을 빠르게 만들어주는 방법이다.
1차 포문으로 값을 빠르게 찾을 수 있는 해쉬의 장점을 잘 생각해보자.

스파이

스파이의 의상 경우의 수 문제
1. 의상 카테고리가 1개가 아닌경우 경우의 수로 접근하여 고르지 않는 경우를 포함한 모든 고르는 경우의 수를 구한 다음, 모든 카테고리에서 고르지 않는 1개의 경우를 뺀다.
2. 예외 사항으로 카테고리가 1개만 존재하는 경우, 카테고리에 해당하는 의상의 개수를 리턴한다.

def get_cats(clothes, dic):
    for item, category in clothes:
        if category in dic:
            dic[category] += 1
        else:
            dic[category] = 1
    return 1
    


def solution(clothes):
    dic = {}
    get_cats(clothes,dic)
    answer = 0
    
    
    _ = 0
    if len(dic.keys()) >= 2: # 카테고리가 2개 이상인 경우
        _ = 1
        for value in dic.values():
            _ = _ * (value+1)
        answer = _ - 1
    
    else: # 카테고리가 1개인 경우
        answer = dic[clothes[0][1]]
    
    return answer

이건 쉬웠다.
걍 파이썬 딕셔너리를 활용하는 경우의 수 문제