[프로그래머스] 고득점 kit - 해시

<문제링크>

https://school.programmers.co.kr/learn/courses/30/parts/12077

프로그래머스

 

<풀이 전략>

1. 완주하지 못한 선수: 동명이인 때문에 set을 쓰면 안되고 dict이나 counter 자료형을 써야한다. hash 자료형을 안 쓰고 그냥 list나 zip등을 써도 통과된다.

2. 폰켓몬: set을 쓰면 쉽다

3. 전화번호 목록: 해쉬를 안 쓰고 list를 써서 O(N)에 풀이했다. 해쉬를 쓴 풀이도 봤는데 그냥 list를 쓰는 게 더 쉬울 것 같다

4. 위장: defaultdict을 활용했다. 전체 경우의 수를 파악하는 과정이 있어서 해쉬보다 수학 문제에 더 가까운 문제

5. 베스트앨범: sort의 key값으로 lambda를 활용해서 조건에 맞게 정렬해주는 게 핵심이다.

 

<정답코드>

# 1. 완주하지 못한 선수

def solution(participant, completion):
    answer = ''
    
    ans_dict = {}
    hash_val = 0
    
    for p in participant:
        ans_dict[hash(p)] = p
        hash_val += hash(p)
    
    for c in completion:
        hash_val -= hash(c)

    answer = ans_dict[hash_val]

    return answer

 

# 2. 폰켓몬

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

 

# 3. 전화번호 목록

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book) - 1):
        if phone_book[i] == phone_book[i + 1][:len(phone_book[i])]:
            answer = False
            break
            
    return answer

 

# 4. 위장

from collections import defaultdict

def solution(clothes):
    clothes_dict = defaultdict(int)
    
    for c in clothes:
        clothes_dict[c[1]] += 1
    
    answer = 1
    
    for type in clothes_dict:
        answer *= (clothes_dict[type] + 1)
    
    answer -= 1
    
    return answer

 

# 5. 베스트 앨범

from collections import defaultdict

def solution(genres, plays):
    genre_play = defaultdict(int)
    
    for i in range(len(genres)):
        genre_play[genres[i]] += plays[i] 
    
    genres = list(enumerate(genres))
    temp = list(zip(genres, plays))
    
    temp.sort(key = lambda x : x[0][0])
    temp.sort(key = lambda x:(genre_play[x[0][1]], x[1]), reverse=True)
    
    genre_count = defaultdict(int)
    answer = []
    
    for (info, play) in temp:
        if genre_count[info[1]] >= 2:
            continue
            
        answer.append(info[0])
        genre_count[info[1]] += 1

        
    return answer