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

https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 

코딩테스트 연습 - 베스트앨범

Fact Finding

---

• 해시의 자료구조 이용
• 장르, play 횟수, 노래의 고유 번호 정보를 다 가지고 있는 자료 구조를 구축하는 것이 필요
• 노래를 수록하는 기준을 전부 적용해주어야

Time Complexity

---

• 장르 구축 O(n)
• 자료구조 구축 O(n)
• 장르 sorted 정렬 O(nlogn)
• 최종 정렬 O(x*nlogn) (x = key 갯수, 단 x < 100)
• 최종 Time Complexity == O(nlogn)

한계점

---

• 정렬에 너무 의존
• 데이터가 훨씬 크면 상당한 시간 복잡도를 소모할 것
• 복잡도 분석이 맞는 지 의문..

 

구현 코드

def solution(genres, plays):
    genre = {}
    play_genre = {}
    for ge in genres : genre[ge] = 0 # O(n)
    for i in range(len(genres)) : # O(n)
        genre[genres[i]] += plays[i] 
        play_genre[(plays[i],i)] = genres[i]
    keys = genre.keys()
    keys = sorted(keys, key=lambda x : genre[x], reverse=True) # O(nlogn)
    answer = []
    for key in keys :  # key갯수 = x, O(x*nlogn)
        agg = []
        for song in play_genre : 
            if play_genre[song] == key : 
                agg.append(song)
        agg = sorted(agg, key = lambda x : (x[0],-x[1]), reverse=True)
        for i in range(len(agg)) : 
            answer.append(agg[i][1])
            if i == 1 : break
    return answer