베스트앨범(해시)

프로그래머스 베스트앨범

level3

프로그래머스의 베스트앨범 문제였다. 해시를 이용해 빠른 시간복잡도로 풀어내야 되는 문제.

두 개의 딕셔너리를 사용해야 한다.

먼저 장르를 key로 삼아 각 장르가 몇번씩 플레이 되었는지, 딕셔너리에 저장해준다.

each_play 딕셔너리에는 리스트를 저장해 주는데, 이 리스트는 현재 장르에서 가장 많이 재생된 곡과 인덱스를 계속 업데이트 해주는 리스트이다.

for 문을 돌면서 장르 딕셔너리에는 장르가 나올 때마다 play 횟수를 더해주고, each_play 딕셔너리에는 최고 횟수의 플레이 인덱스를 저장해준다.

그리고 장르 딕셔너리만 정렬해주면 해당 장르의 each_play 딕셔너리의 값을 순서대로 빼와서 답을 리턴해주면 된다.

def solution(genres, plays):
    genres_play = {}
    each_play = {}
    ans = []
    for i in range(len(genres)):
        if genres[i] not in genres_play:
            genres_play[genres[i]] = plays[i]
            each_play[genres[i]] = [[plays[i], i], [-1, -1]]
        else:
            genres_play[genres[i]] += plays[i]
            if plays[i] > each_play[genres[i]][0][0]:
                each_play[genres[i]][1] = each_play[genres[i]][0]
                each_play[genres[i]][0] = [plays[i],i]
            elif plays[i] > each_play[genres[i]][1][0]:
                each_play[genres[i]][1][0] = plays[i]
                each_play[genres[i]][1][1] = i
            else:
                continue

    temp = sorted(genres_play.items(), key=lambda x: -x[1])

    for k, v in temp:
        if each_play[k][1][0] == -1 and each_play[k][1][0] == -1:
            ans.append(each_play[k][0][1])
        elif len(each_play[k]) == 2:
            ans.append(each_play[k][0][1])
            ans.append(each_play[k][1][1])

    return ans