[프로그래머스/Python] 베스트앨범

dictionary 하나로 풀어보려고 했는데 도저히 각이 안나와서 그냥 dictionary 2개를 썼다

그래서 풀이가 좀 더럽긴하지만,, 일단 맞았으니 올려본다

def solution(genres, plays):
    album_by_genre = {} # genre, (play, index)
    plays_by_genre = {} # (genre, plays)
    for i, play in enumerate(plays):
        g = genres[i]
        if g in plays_by_genre:
            plays_by_genre[g] += play
            album_by_genre[g].append((play, i))
        else:
            plays_by_genre[g] = play
            album_by_genre[g] = [(play, i)]
    for k, v in album_by_genre.items():
        album_by_genre[k] = sorted(v, key=lambda x: x[0], reverse=True)
    
    gp = sorted(plays_by_genre.items(), key = lambda x: x[1], reverse= True)

    answer = []
    for genre, _ in sorted(plays_by_genre.items(), key = lambda x: x[1], reverse= True):
        t = 0
        for play, index in album_by_genre[genre]:
            if t < 2:
                t += 1
                answer.append(index)
    
    return answer

0. 장르별 재생된 횟수 총합을 저장하는 딕셔너리, 장르별 (횟수, 인덱스) 쌍을 저장하는 딕셔너리를 만들었다.

1. 첫 for문을 돌면서 장르별 재생 횟수 총합을 계산하고, album_by_genre 딕셔너리에 데이터를 집어넣는다.

2. album_by_genre 를 각각 재생 횟수별로 정렬해주기 위해 for문을 다시 돈다.

3. plays_by_genre도 재생 횟수 총합을 기준으로 내림차순으로 정렬해준다.

4. for문을 돌면서 재생횟수 총합이 많은 장르 순대로, 노래별 재생 횟수가 많은 고유번호를 최대 2개까지 넣어준다.

 

 

시간 복잡도

정렬: O(nlogn)

for문: O(n)

=> O(n²logn)

별로인 풀이...ㅎ..

 

다른 사람 풀이

- 이중 람다

def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
    genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
    return answer

처음에 내가 풀고 싶었던 풀이를 그대로 옮겨놓았다.

(play, index)만 저장하고, sum을 이용해 sort하고 싶었다. 근데 방법을 몰라서 결국 sum을 하는 dictionary를 별도로 만든거였는데

이중 람다가 방법이었다!!!

genreSort -> 재생횟수 총합으로 장르 기준 정렬

• x: 장르
• d[x]: 해당 장르의 (play, index) 배열
• y: d[x] 배열의 원소. 즉, (play, index)
• y[0]는 play

for genreSort -> 재생횟수 많고 횟수가 같다면 고유 번호가 낮은 노래 골라서 수록

min(len(temp),2) -> 와우... 최대 2개, 적다면 그 길이대로

 

- class 활용

def solution(genres, plays):
    answer = []
    dic = {}
    album_list = []
    for i in range(len(genres)):
        dic[genres[i]] = dic.get(genres[i], 0) + plays[i]
        album_list.append(album(genres[i], plays[i], i))

    dic = sorted(dic.items(), key=lambda dic:dic[1], reverse=True)
    album_list = sorted(album_list, reverse=True)



    while len(dic) > 0:
        play_genre = dic.pop(0)
        print(play_genre)
        cnt = 0;
        for ab in album_list:
            if play_genre[0] == ab.genre:
                answer.append(ab.track)
                cnt += 1
            if cnt == 2:
                break

    return answer

class album:
    def __init__(self, genre, play, track):
        self.genre = genre
        self.play = play
        self.track = track

    def __lt__(self, other):
        return self.play < other.play
    def __le__(self, other):
        return self.play <= other.play
    def __gt__(self, other):
        return self.play > other.play
    def __ge__(self, other):
        return self.play >= other.play
    def __eq__(self, other):
        return self.play == other.play
    def __ne__(self, other):
        return self.play != other.play

pytonic 그 자체..

class 끼리 비교하는 기준을 세움