프로그래머스 Lv.3: 베스트앨범 - Python 풀이

문제 설명

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

프로그래머스

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

문제 요약) 각 장르에서 노래를 2개씩 뽑을 건데 1. 장르의 총 재생수가 큰 장르부터 2. 장르에서 재생수가 큰 노래부터 3. 재생수가 같으면 고유 번호 낮은 것부터 수록합니다. 이때 수록된 노래의 고유 번호를 순서대로 리턴합니다.

풀이 과정

우선 1번 규칙을 만족시키기 위해 어떤 장르의 누적 재생수가 가장 큰지를 알아야 합니다. 이건 하나씩 돌면서 누적해서 구해야 할 것 같습니다.

그 다음에는 2번 규칙을 만족시키기 위해 노래를 재생수를 기준으로 내림차순 정렬을 합니다. 장르, 재생 횟수, 고유 번호를 모두 기억하고 있어야 하기 때문에 튜플 같은 걸로 묶어서 저장하고, sort의 lamba 함수를 써서 이 3개의 값 중 ‘재생수’를 기준으로 정렬합니다.

마지막으로 한 장르에서 노래를 최대 2개씩 뽑아야 하니까, limit 값을 두고 한 곡씩 수록할 때마다 이 변수 값을 업데이트하겠습니다.

정답 코드

def solution(genres, plays):
    answer = []
    
    # 장르의 개수를 구하기 위해 중복을 제거하는 집합을 사용
    genres_set = set(genres)
    # 장르 이름과 장르의 누적 재생 횟수를 담기 위한 딕셔너리 생성
    genres_sum = {}
    # 딕셔너리 초기화
    for genre in genres_set:
        # 키: 장르 이름, 값: 누적 재생 횟수
        genres_sum[genre] = 0
    
    # 노래의 고유 번호, 장르 이름, 재생 횟수를 담기 위한 리스트 생성
    song_info = []
    # 고유 번호 업데이트를 위한 변수 생성
    index = 0
    # 장르와 재생 횟수를 묶어서 튜플로 만들어주는 zip 사용
    for pair in zip(genres, plays):
        # 맨앞에 고유 번호 붙여서 총 3개의 값이 들어가는 튜플이 됨
        pair = (index,) + pair
        # 튜플을 리스트에 추가
        song_info.append(pair)
        # 해당 장르 이름을 키로 가지는 값에 재생 횟수를 누적
        genres_sum[pair[1]] += pair[2]
        # 고유 번호 업데이트
        index += 1
        
    # 재생 횟수를 기준으로, 내림차순 정렬
    song_info.sort(key=lambda x: x[2], reverse=True)
    # 장르의 누적 재생 횟수를 기준으로, 내림차순 정렬
    # sorted 함수 때문에 리스트로 변환됨
    # 이때, items()를 사용해서 키와 밸류 모두를 가지고 간다 -> (키, 밸류) 튜플 형태가 됨
    genres_sum = sorted(genres_sum.items(), key=lambda x: x[1], reverse=True)

    # 장르 개수만큼 반복
    for i in range(len(genres_set)):
        # 최대 2개까지만 수록하기 위한 변수 생성
        limit = 0
        # 노래 개수만큼 반복
        for j in range(len(song_info)):
            # 노래의 장르가 genres_sum의 장르랑 같고, 수록된 노래가 2개 미만이면
            if song_info[j][1] == genres_sum[i][0] and limit < 2:
                # 해당 노래의 고유 번호를 answer에 추가
                answer.append(song_info[j][0])
                # 수록했으니 제한 + 1
                limit += 1
    
    return answer

기억하고 있어야 할 값이 많아서 (고유 번호, 장르 이름, 재생 횟수) 이렇게 3개의 값을 묶는 튜플 형태를 활용했습니다.

song_info는 재생 횟수를 기준으로 내림차순 정렬, genres_sum은 장르별 누적 재생 횟수를 기준으로 내림차순 정렬을 했기 때문에, 마지막에 for문에서는 song_info의 장르명과 genres_sum의 장르명이 같다는 것만 확인하면 됩니다.

배운 점

• 딕셔너리를 정렬하려면 sorted() 함수를 사용해야 한다. key나 reverse는 sort 함수랑 똑같이 사용하면 된다. 이때 sorted()의 반환값은 리스트다.
• sorted()의 인자로 딕셔너리 그 자체만 넣으면 딕셔너리의 키 값들만 들고 있는 리스트가 된다. 그래서 키와 밸류 모두 가지고 가고 싶으면 items() 함수를 사용한다. 이렇게 하면 (키, 밸류) 형태의 리스트로 나온다.

로직은 간단한데 데이터를 어떻게 들고 있어야 할지 생각이 필요했던 문제였습니다.

 

이상입니다.