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

https://programmers.co.kr/learn/courses/30/lessons/42579

프로그래머스

---

[풀이]

 

(1) PSUM : 장르별 총 재생횟수를 비교한다. => PSUM을 내림차순 정렬한다.

PSUM은 딕셔너리이며

키(Key)값은 장르이고, Value값은 해당장르를 재생한 횟수들의 총 합이다.

 

(2) G[장르] =[ (재생횟수1, 고유번호1), (재생횟수2, 고유번호2) ... ] & 장르별 노래선택

[ 노래를 선택 최대 횟수 ]

장르에 있는 노래들을 리스트에 넣는다.

여기서 주의해야할게 장르별로 최대 2곡의 노래를 선택할 수 있다.

그래서 노래를 선택할 수 있는 최대값은 len(PNUM)*2 번이다.

len(PNUM)은 장르(딕셔너리의 키값)의 개수이기도 하다.

나는 노래를 선택할 수 있는 최댓값을 total_cnt라고 정의했다.

 

그리고 각 장르별로 노래를 선택했을 때마다

total_cnt가 0인지를 확인한다.

total_cnt가 0이라면 그때까지 모은 노래고유번호 리스트(answer)을 리턴한다.

모든 장르를 탐색해도 total_cnt가 0보다 큰 경우가 있을 수 있다. (이때도 마찬가지로 answer을 리턴)

 

[장르별 노래 선택]

(2-1) 장르에 있는 노래가 1개인 경우

1개의 노래를 pop()하고, answer에 append를 한다.

total_cnt에서 -1을 뺀다.

 

(2-2) 장르에 있는 노래가 2개이상인 경우

  - G[장르]의 리스트를 정렬한다.

    정렬기준

     1) 재생횟수를 오름차순으로 정렬

     2) 재생횟수가 동일한 경우 -> 고유번호가 큰 것을 우선으로 한다. 

   

    왜 이렇게 정렬을 했냐면 pop을 할때 python에서 복잡도는 O(1)이다.

    "재생횟수기준으로 내림차순 정렬", "재생횟수 동일할 때, 고유번호가 작은 것을 기준으로 정렬"로도 가능하다.

    그런데 pop연산을 할때 pop(0)를 해야한다. pop(0)의 복잡도는 O(N)이다.

 

G['classic']=[ (400,1) , (400,2) , (500,3) ] 이라하자

 

* 내가 푼 방식대로 정렬을 하면

( "재생횟수기준으로 오름차순 정렬", "재생횟수 동일할 때, 고유번호가 큰 것을 기준)

G['classic']= [ (400,2), (400,1), (500,3)]

G['classic'].pop() => (500,3)이다.

 

* 내가 푼 방식의 반대로 한 경우

( "재생횟수기준으로 내림차순 정렬", "재생횟수 동일할 때, 고유번호가 작은 것을 기준")

G['classic']= [ (500, 3), (400, 1), (400, 2)]

G['classic'].pop() => (400,2) 이고, G['classic'].pop(0)=(500,3) 이다.

 

- 최대 2번을 pop한다.

- pop할 때 주의할 점은 현재 장르의 음악개수가 0보다 크고, total_cnt가 0보다 크고, 

초기 G[장르]의 길이가 2이상일때 최대 2개의 음악만 선택이 가능하므로 cnt도 0보다 커야

음악을 선택할 수 있다.

 

 

ex)

genres=['classic', 'classic', 'jazz', 'jazz', 'pop', 'pop']

plays=[400, 500, 200, 200, 300, 300]

PSUM=[ 'classic':900, 'pop':600, 'jazz':400] => 각 장르별로 2개씩 선정가능 => 최대 3*2=6개 선택가능

G[classic]=[(0,400), (1,500)] => 1,0 선택

G[pop]=[(5,300), (4,300)] => 5,4 선택

G[jazz]=[(3,200),(2,200)] => 2,3 선택

answer=[1,0,5,4,2,3]

---

[코드 python3]

def solution(genres, plays):
    G={}
    PSUM={}
    for idx, (g,p) in enumerate(zip(genres, plays)):
        #장르별 재생횟수 구하기
        if g not in PSUM:
            PSUM[g]=0
        PSUM[g]+=p
        
        #장르에 있는 노래 (재생횟수, 고유번호) 정보 넣기
        if g not in G:
            G[g]=[]
        G[g].append((p,idx)) #(재생횟수, 고유번호)
    
    #먼저 PSUM을 내림차순 정렬 :정렬기준(장르별 재생횟수)
    PSUM=sorted(PSUM.items() , key=lambda x: -x[1])
    
    answer = []
    total_cnt=2*len(PSUM) #최대 2*len(PSUM)번 선택가능
    for psum in PSUM:
        if total_cnt==0:
            return answer
        
        g=psum[0] #g: 장르
        #장르별 노래가 한곡만 있다면
        if len(G[g])==1:
            _, idx=G[g].pop()
            answer.append(idx)
            total_cnt-=1

        #장르별 노래가 두곡이상이다.
        elif len(G[g])>=2:
            #pop(0)는 O(N)이므로 pop의 복잡도를 줄이기 위해서...
            #장르별 노래 정렬 : 정렬기준(재생횟수 오름차순/ 고유번호: 내림차순)
            G[g]=sorted(G[g], key=lambda x: (x[0], -x[1]))
            cnt=2
            while len(G[g])>0 and cnt>0 and total_cnt>0:
                cnt-=1
                total_cnt-=1
                _, idx= G[g].pop()
                answer.append(idx)
                
    return answer

 

 

(업데이트 코드)

- 업데이트 사항: while문 수정

- G[g]가 1개일때/ 2개이상일때 구분없이 한번에 처리.

def solution(genres, plays):
    G={}
    PSUM={}
    for idx, (g,p) in enumerate(zip(genres, plays)):
        #장르별 재생횟수 구하기
        if g not in PSUM:
            PSUM[g]=0
        PSUM[g]+=p
        
        #장르에 있는 노래 (재생횟수, 고유번호) 정보 넣기
        if g not in G:
            G[g]=[]
        G[g].append((p,idx)) #(재생횟수, 고유번호)
    
    #먼저 PSUM을 내림차순 정렬 :정렬기준(장르별 재생횟수)
    PSUM=sorted(PSUM.items() , key=lambda x: -x[1])
    
    answer = []
    total_cnt=2*len(PSUM) #최대 len(PSUM)*2번
    for psum in PSUM:
        if total_cnt==0:
            return answer
        
        g=psum[0] #g: 장르
        cnt=2
        while total_cnt>0 and cnt>0 and len(G[g])>0:
            G[g]=sorted(G[g], key=lambda x: (x[0], -x[1]))
            _, idx= G[g].pop()
            answer.append(idx)
            cnt-=1
            total_cnt-=1
            
    return answer

 

---

[실패코드]

5번~14번 테스트케이스에서 실패가 떴다. (33.3점)

def solution(genres, plays):
    G={}
    PSUM={}
    for idx, (g,p) in enumerate(zip(genres, plays)):
        #장르별 재생횟수 구하기
        if g not in PSUM:
            PSUM[g]=0
        PSUM[g]+=p
        
        #장르에 있는 노래 (재생횟수, 고유번호) 정보 넣기
        if g not in G:
            G[g]=[]
        G[g].append((p,idx)) #(재생횟수, 고유번호)
    
    #먼저 PSUM을 내림차순 정렬 :정렬기준(장르별 재생횟수)
    PSUM=sorted(PSUM.items() , key=lambda x: -x[1])
    
    answer = []
    total_cnt=4 #최대4번 선택가능 => 장르별로 2개씩이므로 여기가 원인임.
    for psum in PSUM:
        if total_cnt==0:
            return answer
        
        g=psum[0] #g: 장르
        #장르별 노래가 한곡만 있다면
        if len(G[g])==1:
            _, idx=G[g].pop()
            answer.append(idx)
            total_cnt-=1

        #장르별 노래가 두곡이상이다.
        elif len(G[g])>=2:
            #pop(0)는 O(N)이므로 pop의 복잡도를 줄이기 위해서...
            #장르별 노래 정렬 : 정렬기준(재생횟수 오름차순/ 고유번호: 내림차순)
            G[g]=sorted(G[g], key=lambda x: (x[0], -x[1]))
            cnt=2
            while len(G[g])>0 and cnt>0 and total_cnt>0:
                cnt-=1
                total_cnt-=1
                _, idx= G[g].pop()
                answer.append(idx)
                
    return answer