[Programmers/알고리즘 고득점 KIT] 베스트앨범

[Programmers] 베스트앨범

Level 3 | #해시 #정렬

문제 바로가기 🔗

1. 문제 요약

스트리밍 사이트에서 장르별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시한다.

노래 선정 기준은 다음과 같다: 속한 노래가 많이 재생된 장르 → 장르 내에서 많이 재생된 노래 → 재생 수가 같다면 고유 번호가 낮은 노래 순서이다.

2. 핵심 포인트

• ✅ 데이터 그룹화: defaultdict를 사용하여 장르별 총 재생 수와 곡 정보를 한 번에 정리한다.
• ✅ 다중 조건 정렬: Python의 sorted 함수와 lambda를 활용하여 복잡한 정렬 우선순위를 처리한다.

3. 구현 코드 (Python)

from collections import defaultdict

def solution(genres, plays):
    play_count = defaultdict(int)
    genre_songs = defaultdict(list)  # 장르별 곡 그룹핑

    # 1. 한 번의 순회로 데이터 정리
    for i, (genre, play) in enumerate(zip(genres, plays)):
        play_count[genre] += play
        genre_songs[genre].append((play, i))

    # 2. 장르 정렬 (총 재생 수 기준 내림차순)
    sorted_genres = sorted(play_count, key=lambda x: play_count[x], reverse=True)

    answer = []
    # 3. 장르별 상위 2곡 추출
    for genre in sorted_genres:
        # 재생 수 내림차순(-x[0]), 인덱스 오름차순(x[1])
        sorted_songs = sorted(genre_songs[genre], key=lambda x: (-x[0], x[1]))
        for play, i in sorted_songs[:2]:
            answer.append(i)

    return answer

📌 동시 생성: play_count는 장르별 재생 합계를, genre_songs는 곡 리스트를 관리한다.

📌 다중 정렬: key=lambda x: (-x[0], x[1])와 같이 튜플을 반환하면 첫 번째 기준이 같을 때 두 번째 기준으로 정렬한다.

4. 데이터 시각화

# play_count 예시

{'pop': 3100, 'classic': 1450}

# genre_songs 예시

{'classic': [(500, 0), (150, 2), (800, 3)], 'pop': [(600, 1), (2500, 4)]}