[알고리즘] 해시(Hash) 프로그래머스 3단계 - 베스트 앨범

def solution(genres, plays):
    
    # 장르별로 가장 많이 재생된 노래 2개
    # 1. 속한 노래가 많이 재생된 장르 
    # 2. 장르 내에서 많이 재생된 노래 
    # 3. 재생 횟수가 같은 경우 고유 번호가 낮은 노래
    
    # { 장르 : 총 재생 횟수 }
    # { 장르 : [(고유번호, 재생횟수), (고유번호, 재생횟수)]}
    
    playDic = {}
    musicDic = {}
    
    for i in range(len(genres)):
        playDic[genres[i]] = playDic.get(genres[i], 0) + plays[i]
        musicDic[genres[i]] =  musicDic.get(genres[i], [])+ [(i, plays[i])]
    
    sortPlayDic = sorted(playDic.items(), key=lambda x:x[1], reverse=True)
    
    answer = []
    for i, j in sortPlayDic:
        musicDic[i] = sorted(musicDic[i], key=lambda x:(-x[1],x[0]))
        answer += [x for x, y in musicDic[i][0:2]]
    
    return answer

풀이과정

1. 총 재생 횟수, 플레이 횟수, 고유 번호 순서대로 수록
   ⇒ { 장르: 총 재생 횟수 }, { 장르: [(고유번호, 재생횟수)] }
   ⇒ 두 종류의 Hash를 만든다.
2. 첫 번째 Dictionary를 총 재생 횟수 내림차순으로 정렬한다.
3. 정렬한 값을 기준으로 두 번째 Dictionary에서 값을 찾고 재생횟수, 고유번호 순서대로 내림차순, 오름차순 정렬한다.
4. 새 배열을 만들어 차례대로 값을 넣는다.

새로 배운 내용

배열의 덧셈

[1, 2] + [3, 4] = [1, 2, 3, 4]
[(1, 2)] + [(3, 4)] = [(1, 2), (3, 4)]

append와 다른 점은 append는 [ ] 즉, 배열 자체를 추가한다.

Dictionary의 get

Dictionary는 Key값을 가지고 Value를 얻는 두 가지 방법이 있다.

dic = {'a': 1, 'b': 2 }

dic['a'] = 1
dic.get('a') = 1
dic.get('c', 0 ) = 0  
// get은 두 번째 인자로 값이 없을 경우를 대비할 수 있다.

또한, Dictionary는 Key값이 중복될 수 없어 원래 요소를 덮어쓴다.
누적으로 더하는 풀이에서 사용될 수 있다.

lambda 함수

lambda x:-x[0]  // 내림차순
lambda x:x[0]   // 오름차순

2차 풀이

def solution(genres, plays):

    # total_dic { 장르: 총 재생 횟수 }
    # play_dic { 장르: [(고유번호, 재생횟수)] }

    total_dic = {}
    play_dic = {}

    for i in range(len(genres)):
        total_dic[genres[i]] = total_dic.get(genres[i], 0) + plays[i]
        play_dic[genres[i]] = play_dic.get(genres[i], []) + [(i, plays[i])]
    
    total_sort = sorted(total_dic.items(), key=lambda x: -x[1])

    result = []
    for i, j in total_sort:
        play_dic[i] = sorted(play_dic[i], key=lambda x: (-x[1], x[0]))
        for k in play_dic[i][0:2]:
            result.append(k[0])
    
    return result