베스트앨범

• 풀이 자체는 그냥 시키는 대로 구현하면 된다.
• 그냥 이것저것 조건이 많아서 구현이 조금 지저분해지기 쉬운데, 어떻게 하면 좀 더 깔끔해질지를 생각할 여지는 있다
• 시간 복잡도는 데이터를 전부 읽는데 O(n), 장르들을 정렬하는 데에, O(mlogm)이 필요하다. 장르마다 재생횟수가 많은 top2를 골라야 하는데 각각 정렬해서 찾으려고 하면 코드는 짧아지지만 O(nlogn)이 추가된다. 정렬하지 않고 그냥 리니어 서치로 top2를 찾으면 모든 장르에서 다 찾는데에 O(n)이니까 총 시간복잡도가 O(n+mlogm)

"""Solution code for "Programmers 42579. 베스트앨범".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42579
- Solution link: http://www.teferi.net/ps/problems/programmers/42579
"""

import collections


def solution(genres, plays):
    songs_by_genre = collections.defaultdict(list)
    for song, genre in enumerate(genres):
        songs_by_genre[genre].append(song)
    answer = []
    for songs in sorted(songs_by_genre.values(),
                        key=lambda songs: -sum(plays[song] for song in songs)):
        answer.append(max(songs, key=lambda song: plays[song]))
        if len(songs) > 1:
            plays[answer[-1]] = -1
            answer.append(max(songs, key=lambda song: plays[song]))
    return answer