알고리즘 with python.08

멜론 베스트 앨범 뽑기

조건 정의
1.속한 노래가 많이 재생된장르를 먼저 수록한다.(단, 각 장르에 속한 노래의재생 수 총합은 모두 다르다.
2.장르 내에서 많이 재생된 노래를 먼저 수록한다.
3.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.

코드

genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]


def get_melon_best_album(genre_array, play_array):
    n = len(genre_array)
    genre_total_play_dict = {}
    genre_index_play_array_dict = {}
    for i in range(n):
        genre = genre_array[i]
        play = play_array[i]
        if genre not in genre_total_play_dict:
            genre_total_play_dict[genre] = play
            genre_index_play_array_dict[genre] = [[i, play]]
        else:
            genre_total_play_dict[genre] += play
            genre_index_play_array_dict[genre].append([i, play])

    print(genre_total_play_dict)
    print(genre_index_play_array_dict)

    sorted_genre_play_array = sorted(genre_total_play_dict.items(), key=lambda item: item[1], reverse=True)
    print(sorted_genre_play_array)
    result = []
    for genre, _value in sorted_genre_play_array:
        index_play_array = genre_index_play_array_dict[genre]
        sorted_by_play_and_index_play_index_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
        for i in range(len(sorted_by_play_and_index_play_index_array)):
            if i > 1:
                break
            result.append(sorted_by_play_and_index_play_index_array[i][0])
    return result


print(get_melon_best_album(genres, plays))

우선,속한 노래가 가장 많이 재생된 장르를 찾아보겠습니다.
그걸 알기 위해서는 장르별 재생 수를 더해야 하는데, 장르별(Key)로 재생 수(Value)를 더하고 관리하기 위해서는 딕셔너리를 사용해야 된다.
장르 별 곡의 정보를 저장하기 위해서 장르별 Key에, 재생 수와 인덱스를 배열로 묶어 배열에 저장합니다.
재생 수와 인덱스를 저장하는 이유: 재생 수로 정렬해야 하고, 들어가는 노래의 인덱스를 반환해야 해서 둘 다 필요하기 때문이다.