[알고리즘] 베스트앨범 프로그래머스 Lv3. 파이썬

코드: https://github.com/ddalkyTokky/Algorithm_test/blob/main/Python3/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/42579.%E2%80%85%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94/%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94.py

 

1. 정렬

해시는 모르곘고.. 그냥 정렬하면 될 것 같았고 실제로도 정렬해서 풀었다.. 뭔가 다른 풀이가 있나 찾아봐야곘다.

 

2. 최종 코드

그냥, 집계를 가장 먼저 냈다.

statics = [음악 번호, 장르(string), 해당 음악이 속한 장르의 총 재생 횟수, 해당 곡의 재생 횟수]

 

람다식을 이용해 다음과 같은 우선순위를 두어 정렬한다.

 해당 음악이 속한 장르의 총 재생 횟수(내림)
해당 곡의 재생 횟수(내림)
음악 번호(오름)

그 다음, 각 장르별 최대 2곡씩만 최종 결과에 넣을 수 있기 때문에 다시 한번 집계를 순회하면서 같은 장르가 2곡 이상 들어간 것만 리스트에서 솎아낸다. (정확히는 2곡까지만 새로운 리스트에 집어 넣는다.)

def solution(genres, plays):    
    n = len(genres)
    gd = {}

    for idx in range(n):
        if(genres[idx] in gd):
            gd[genres[idx]] += plays[idx]
        else:
            gd[genres[idx]] = plays[idx]
    
    statics = []
    for idx in range(n):
        statics.append([idx, genres[idx], gd[genres[idx]], plays[idx]])
    
    statics.sort(key = lambda x :(-x[2], -x[3], x[0]))
    
    cd = {}
    answer = []
    for static in statics:
        if(static[1] in cd):
            if(cd[static[1]] == 1):
                cd[static[1]] += 1
                answer.append(static[0])
        else:
            cd[static[1]] = 1
            answer.append(static[0])
    
    return answer

3. 시간 복잡도

행위	시간 복잡도
장르별 총 재생 횟수 구하기	O(N)
집계 내기	O(N)
정렬하기	O(3NlogN)
집계 순회하면서 2개 이상인 곡 빼기	O(N)
최종	O(NlogN)