[Python][Hash] 베스트앨범 - 프로그래머스 level 3

[문제]

출처 : https://programmers.co.kr/learn/courses/30/lessons/42579

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예 genres plays return

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

[알고리즘]

• 해쉬 알고리즘이다. 
• 파이썬의 Dictionary 데이터 구조를 사용한다. 
• key 는 장르명, value는 [고유번호, 재생횟수] 의 리스트로 되어있는 2차원 리스트로 설정하였다.

방법

1. Dictionary의 value의 list를 재생 횟수를 기준으로 정렬
2. Dictionary의 각 element마다 value의 재생 횟수를 더한 값을 저장하는 리스트 생성, 이는 장르 정렬을 위함임
   • 리스트 [장르명, 그 장르의 총 재생 횟수]의 2차원 리스트 생성
3. 위에서 구한 리스트를 정렬
4. 위 리스트를 반복하여 정렬된 장르안에서의 재생 횟수로 정렬된 고유번호 획득

 

[느낀 점 / 깨달은 점]

• lambda 함수를 배웠다.
  • lambda 함수는 이름없는 함수이다. 보통 특정 한 곳에서만 사용할 때 쓰이고, 메모리를 잡지 않기에 간단하게 사용할 수 있다. 
  • 보통 정렬의 조건을 정해줄 때 많이 쓰인다.
  • 문법은 다음과 같다. 
    기본 함수 문법 --> def f (매개변수) return 결과 
    lambda 함수 문법 --> f = lambda 매개변수 : 결과 
    
    def f(x) return x+1 기본 함수 문법이 다음과 같다면 lambda는
    f = lambda x : x+1 이다. 
    f(10)  를 출력하면 두개 모두 11이 출력될 것이다.
    
    
  • 정렬하고 싶은 리스트가 두개의 값을 가지고 있을 때 두번째 값을 기준으로 정렬하는 예시는 다음과 같다.
    
    a = [(5, 1), (0, 1), (1, 2), (3, 0),  (5, 2)]
    b = sorted(a, key = lambda x : x[1])
    
    => b [(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]
    
    
  • 그러나, 여기서 두번째값 다음으로 첫번째값으로도 추가로 정렬하고 싶다면! 다음과 같다.
    
    a = [(5, 1), (0, 1), (1, 2), (3, 0),  (5, 2)]
    c = sorted(a, key = lambda x : (x[1], x[0]))
    
    => c [(3, 0), (0, 1), (5, 1), (1, 2), (5, 2)]
    
    
  • 딕셔너리에서 key나 value로 정렬
    
    key로 정렬 
    a = sorted(dict.items(), key = lambda x : x[0])
    value로 정렬 
    a = sorted(dict.items(), key = lambda x : x[1])

 

• 코드(다른 사람 풀이 참고 (- , - , 유민우 , incuriositas , - 외 1 명))

def solution(genres, plays):
    answer = []
    
    d = {}
    for i in range(len(genres)):
        if not genres[i] in d : 
            d[genres[i]] = []
        d[genres[i]].append([i, plays[i]])
    print(d)
    
    sum_list = []
    for genre in d : 
        d[genre].sort(key = lambda x : x[1], reverse = True)
        sum_list.append([genre,sum([ p for _, p in d[genre]])])
        
    sum_list.sort(key = lambda x : x[1], reverse = True)
    
    for genre, _ in sum_list : 
        answer.extend([i for i, _ in d[genre][:2]])
    
    return answer

 

• 초반 코드(정답, 그러나 깔끔하진 않음)

def solution(genres, plays):
    answer = []
    genre_dict = {} 
    
    for i in range(len(genres)) : 
        if genre_dict.get(genres[i]) is not None : 
            genre_dict[genres[i]] += plays[i]
        else : 
            genre_dict[genres[i]] = plays[i]
    
    sorted_genres = sorted(genre_dict.items(), key = lambda item: item[1], reverse = True)

    genres_order = dict()
    for i in range(len(sorted_genres)):
        genres_order[sorted_genres[i][0]] = i
    
    list_dict = [dict() for _ in range(len(genre_dict))]
    list_dict_sorted =[]
    for i in range(len(genres)) : 
        list_dict[genres_order[genres[i]]][i] = plays[i]
    for i in range(len(list_dict)) :
        list_dict_sorted.append(sorted(list_dict[i].items(), key = lambda item: item[1], reverse=True)[:2])
    
    for i in range(len(list_dict_sorted)) :
        for j in range(len(list_dict_sorted[i])):
            answer.append(list_dict_sorted[i][j][0])
    
    return answer

 

• 두번째 풀었을 때의 코드 (정답, 주의할 점 : list 삭제할 때 동일 index를 갖는 list가 있다면 그 list 또한 잊지 않고 삭제할 것, 초반 풀이와 다르게 numpy 사용)
  list의 지우는 함수는 remove([값]), numpy의 지우는 함수는 delete([배열], [배열의 인덱스])

import numpy as np

def solution(genres, plays):
    answer = []
    
    dict1 = {} # key - 장르, values - [재생 횟수, index]
    dict2 = {} # key - 장르, value - 총 재생 횟수
    for i in range(len(genres)):
        if genres[i] in dict1 : 
            dict1[genres[i]].append([plays[i], i])
            dict2[genres[i]] += plays[i]
        else : 
            dict1[genres[i]] = [[plays[i], i]]
            dict2[genres[i]] = plays[i]
    
    total_plays = list(dict2.items())
    total_plays.sort(key = lambda x : x[1], reverse=True)
    
    for i in range(len(total_plays)):
        a = np.array(dict1[total_plays[i][0]])
        plays = a[:,0]
        indices = a[:,1]
        
        max1 = max(plays)
        index, = np.where(plays == max1)
        
        if len(index) > 1 : # 최대 재생곡이 2개 이상일 떄, 고유 번호가 낮은 노래 순
            
            cands = []
            for j in index :
                cands.append(indices[j])
            min_ind = min(cands)
            answer.append(int(min_ind))
            cands.remove(min_ind)
            answer.append(int(min(cands)))
            
        else : # 최대 재생 곡이 1곡 일 때, 그 다음 최대 재생 곡
            answer.append(int(indices[index[0]]))
            plays = np.delete(plays, index[0])
            indices = np.delete(indices, index[0])
            if len(plays) >=1 : # 그 다음 최대 재생곡이 2곡 이상 일 떄
                
                max2 = max(plays)
                index, = np.where(plays == max2)
                if len(index) > 1 : ## 두번쨰의 최대 재생곡이 2개 이상일 때,
                    cands = []
                    for j in index :
                        cands.append(indices[j])
                    min_ind = min(cands)
                    answer.append(int(min_ind))
                else : 
                    answer.append(int(indices[index[0]]))
    
    return answer