[알고리즘] 2024.09.27 풀이

풀이 사이트: 프로그래머스 고득점 Kit! 

# 해시

📝 의상 (lv 2) - https://school.programmers.co.kr/learn/courses/30/lessons/42578

* 체감 난이도 : ⭐️ - - - -

- 해쉬의 매우 기본적인 문제였다.
- 옷의 종류가 정해져 있고, 중복 된 종류의 옷은 함께 입을 수 없기 때문에 구분해서 저장해야 했다.
- 그렇기 때문에 해쉬를 사용해야하며, Key는 옷의 종류로 하여 저장한다.
- 종류마다 옷들을 리스트 형태로 저장할 필요 없이 단순히 개수만 카운트하면 된다. (얼굴 : 2, 상의 : 3, 하의 : 1 ..)
- 이유는 옷의 경우의 수를 생각보면 알 수 있다.
- 단순하게 생각해봤을때 상의 3가지, 하의 2가지가 있으면 단순 조합수는 6가지이다(2x3).
- 하지만 모든 부위를 입을 필요는 없기 때문에 상의를 입지 않았을 때, 하의를 입지 않았을 때를 포함한 11가지가 답이다.
- 나는 맨살(옷을 입지 않음)을 하나의 옷 종류로 생각하여 상의 4가지, 하의 3가지로 생각했다.
- 하지만 여기서 단 하나의 예외 "하나의 옷은 입어야한다"에 해당하는 경우 1가지를 제외시켜야한다.
- 즉, 4 x 3 - 1  = 12라는 값을 구할 수 있다.
- 딕셔너리를 이용해 단순히 종류별 옷의 개수만 세고, 위의 공식을 이용해서 답을 구했다.

def solution(clothes):
    answer = 1
    
    dic = {}
    
    for i in range(len(clothes)):
        temp_key = clothes[i][1]
        
        if temp_key in dic:
            dic[temp_key] = dic[temp_key] + 1
        else:
            dic[temp_key] = 1
            
    for key in dic:
        answer *= dic[key] + 1
    
    answer -= 1
    
    return answer

 

📝 베스트 앨범 (lv 3) - https://school.programmers.co.kr/learn/courses/30/lessons/42579

* 체감 난이도 : ⭐️⭐️ - - -

- 이게 왜 lv 3인지 당최 모르겠고, 분류도 사실상 정렬 문제라고 생각한다.
- "총 재생 수를 기준으로 장르를 수록", "장르별 많이 재생된 노래 2가지를 수록 (재생수가 같을 경우 고유번호가 작은 순)"라는 2가지 기준을 위해 딕셔너리 두 가지에 장르별 총 재생수와 장르별 각 노래 정보 (고유번호, 재생 수)의 형태로 리스트에 저장했다.
- 풀이는 단순하게 총 재생수로 정렬한 후 두 번째 딕셔너리에서 우선순위가 높은 두 가지 곡의 정보를 뽑아내어 순서대로 answer에 저장하면 된다.
- 요건은 두 번째 딕셔너리에 담긴 각 장르별 노래 정보 리스트를 정렬하는 것이다.
- 나는 cmp_to_key를 지정하여 각 노래 정보 리스트를 정렬했다.
- 먼저 두 곡의 재생 수를 비교하고, 같을 경우 고유번호를 비교하여 더 작은 번호에 우선 순위를 주는 방식으로 설정했다.
- 이후 총 재생수를 기준으로 정렬된 순서에 따라 장르별 노래 2가지를 순서대로 answer에 저장하여 해결했다.

from functools import cmp_to_key

def solution(genres, plays):
    answer = []
    
    dic_count = {}
    dic_inform = {}
    
    for i in range(len(genres)):
        if genres[i] in dic_inform:
            dic_count[genres[i]] += plays[i]
            dic_inform[genres[i]].append([i, plays[i]])
        else:
            dic_count[genres[i]] = plays[i]
            dic_inform[genres[i]] = [[i, plays[i]]]
    sort_genres = sorted(dic_count.items(), key=lambda x: x[1], reverse=True)
    
    for i in range(len(sort_genres)):
        temp_genres = sort_genres[i][0]
        sorted_list = sorted(dic_inform[temp_genres], key=cmp_to_key(compare))
        for j in range(min(len(sorted_list), 2)):
            answer.append(sorted_list[j][0])
        
    return answer

def compare(x, y):
    if x[1] > y[1]:
        return -1
    elif x[1] < y[1]:
        return 1
    else:
        if x[0] < y[0]:
            return -1
        else:
            return 1