프로그래머스

프로그래머스 베스트앨범 풀이: 해시 집계와 우선순위 정렬

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 베스트앨범
  • 출처: 프로그래머스 코딩테스트 연습, 해시
  • 자체 판단 난이도: Level 3

장르별 전체 재생 수와 장르 안에서 선택할 곡의 순서를 서로 다른 기준으로 관리해야 한다. 해시로 그룹별 상태를 모은 뒤 장르 순서와 곡 순서를 각각 정렬해야 하므로 Level 3으로 판단했다.

1. 문제 요약

각 노래에는 고유 번호가 있고, genres[i]는 해당 노래의 장르, plays[i]는 재생 횟수다. 베스트앨범에는 다음 규칙으로 노래를 수록한다.

  1. 전체 재생 수가 많은 장르를 먼저 수록한다.
  2. 같은 장르 안에서는 재생 수가 많은 노래를 먼저 수록한다.
  3. 재생 수가 같다면 고유 번호가 낮은 노래를 먼저 수록한다.
  4. 각 장르에서는 최대 두 곡만 수록하며, 곡이 하나뿐인 장르는 한 곡만 수록한다.

예를 들어 classic의 전체 재생 수가 1,450, pop의 전체 재생 수가 3,100이면 pop을 먼저 처리한다. pop 안에서는 재생 수가 2,500인 고유 번호 4번을 먼저, 그다음 600회인 1번을 선택한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

해시 집계와 그룹별 정렬

두 개의 사전을 사용한다.

  • total_plays[genre]: 장르별 전체 재생 수
  • songs_by_genre[genre]: 해당 장르의 (고유 번호, 재생 수) 목록

노래를 한 번 순회하면서 두 사전을 동시에 갱신한다. 그 후 장르를 전체 재생 수의 내림차순으로 정렬한다. 정렬된 장르 순서대로 곡 목록을 다음 기준으로 정렬한다.

(-재생 수, 고유 번호)

재생 수에는 음수를 사용해 내림차순을 만들고, 고유 번호는 양수 그대로 두어 오름차순을 유지한다. 정렬한 목록의 앞에서 최대 두 곡만 결과에 추가한다.

장르 순위와 곡 순위를 분리하는 이유

장르를 정하는 기준은 대표 곡의 재생 수가 아니라 장르 전체의 재생 합계다. 장르 순위를 먼저 확정한 뒤에는 각 장르 안에서만 곡을 비교하면 된다. 두 단계의 기준을 별도로 집계해야 한 번의 곡 정렬로 장르 순서까지 잘못 정하는 일을 막을 수 있다.

공식 예제에서는 pop의 합계가 3,100, classic의 합계가 1,450이므로 pop이 먼저다. 장르 안의 정렬은 재생 수 내림차순, 동률이면 고유 번호 오름차순이다.

장르 장르 합계 장르 내 정렬 결과 수록 곡
pop 3,100 (4, 2500), (1, 600) 4, 1
classic 1,450 (3, 800), (0, 500), (2, 150) 3, 0

각 장르에서 정렬된 목록의 앞 두 곡만 뽑으면 세 번째 이후 곡은 선택될 수 없다. 곡이 한 개뿐인 장르는 songs[:2]가 있는 곡만 반환하므로 별도 예외 처리가 필요하지 않다.

오답 접근과 반례

장르의 첫 번째 곡 재생 수만 보고 장르 순서를 정하면 장르 전체의 재생 수 조건을 놓친다.

genres = ["a", "a", "b"]
plays = [100, 100, 150]

장르 a의 첫 곡은 100회지만 장르 전체는 200회다. 장르 b는 150회이므로 정답은 a를 먼저 처리하는 순서다. 장르별 합계를 계산하지 않고 대표 곡 하나만 비교하면 b를 먼저 선택하게 되어 틀린다.

장르 안에서 재생 수만 내림차순으로 정렬하고 고유 번호를 고려하지 않는 것도 잘못이다. 재생 수가 같은 곡은 고유 번호가 낮은 곡을 먼저 선택해야 한다.

genres = ["rock", "rock", "rock"]
plays = [100, 300, 300]

장르에서 선택할 순서는 고유 번호 1번, 2번이다. 두 번째 정렬 기준이 없으면 입력 순서나 정렬 구현에 따라 이 조건을 보장할 수 없다.

시간·공간 복잡도

노래 수를 n, 장르 수를 g라고 하자. 장르별 곡 정렬에 필요한 전체 시간은 O(n log n) 이하이고, 장르 정렬에 O(g log g) 시간이 필요하다. g <= n이므로 전체 시간 복잡도는 O(n log n)다.

장르별 곡 목록과 재생 수 합계를 저장하므로 공간 복잡도는 O(n)다.

3. 문제 해결 코드 (Python)

from collections import defaultdict


def solution(genres, plays):
    total_plays = defaultdict(int)
    songs_by_genre = defaultdict(list)

    for song_id, (genre, play_count) in enumerate(zip(genres, plays)):
        total_plays[genre] += play_count
        songs_by_genre[genre].append((song_id, play_count))

    sorted_genres = sorted(
        total_plays,
        key=lambda genre: total_plays[genre],
        reverse=True,
    )

    answer = []
    for genre in sorted_genres:
        songs = sorted(
            songs_by_genre[genre],
            key=lambda song: (-song[1], song[0]),
        )
        answer.extend(song_id for song_id, _ in songs[:2])

    return answer

enumerate의 인덱스가 곧 노래의 고유 번호이므로 별도로 번호를 만들 필요가 없다. 각 장르의 목록에 (song_id, play_count)를 저장하고, 정렬 후 앞의 두 고유 번호만 결과에 추가한다.

total_plays의 키를 정렬하면 장르별 전체 재생 수 순서를 얻을 수 있다. 문제에서 모든 장르의 전체 재생 수가 다르므로 장르 간 동률 처리는 필요하지 않지만, 곡 내부의 동률은 정렬 키의 두 번째 값인 song_id로 처리한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 장르 합계와 장르 내 동률 정렬을 확인할 수 있다.

assert solution(
    ["classic", "pop", "classic", "classic", "pop"],
    [500, 600, 150, 800, 2500],
) == [4, 1, 3, 0]
assert solution(["rock", "rock", "rock"], [100, 300, 300]) == [1, 2]

4. 공식 예제와 추가 검증

공식 예제와 장르 내부 동률, 한 곡 장르, 모든 장르가 한 곡인 경우를 Python 코드로 실행해 확인했다.

공식 예제

입력:
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]

기대 출력: [4, 1, 3, 0]
확인 결과: 통과
검증 목적: 장르 전체 합계와 장르 내부 곡 순서를 함께 확인

추가 검증 1: 장르 내부 재생 수 동률

입력:
genres = ["rock", "rock", "rock"]
plays = [100, 300, 300]

기대 출력: [1, 2]
확인 결과: 통과
검증 목적: 같은 재생 수에서 고유 번호가 작은 곡을 먼저 선택하는지 확인

추가 검증 2: 장르에 곡이 하나뿐인 경우

입력:
genres = ["classic"]
plays = [500]

기대 출력: [0]
확인 결과: 통과
검증 목적: 장르별 최대 두 곡 조건에서 한 곡만 반환하는지 확인

추가 검증 3: 장르 전체 합계로 순서가 바뀌는 경우

입력:
genres = ["a", "a", "b"]
plays = [100, 100, 150]

기대 출력: [0, 1, 2]
확인 결과: 통과
검증 목적: 대표 곡이 아니라 장르별 전체 재생 수로 장르 순서를 정하는지 확인

5. 다른 풀이 방식 검색 및 비교

  • 프로그래머스 공식 문제는 장르 전체 재생 수, 장르 내부 재생 수, 고유 번호를 기준으로 한 수록 순서를 정의한다.
  • kr-goos의 Python 풀이는 장르별 총 재생 수와 장르별 곡 목록을 각각 저장한 뒤 정렬하는 접근을 설명한다.

이 글도 같은 해시 그룹화와 정렬 아이디어를 사용하지만, 정렬 기준을 (-재생 수, 고유 번호) 하나의 키로 명시해 장르 내부 동률 처리를 코드에서 직접 드러냈다. 힙으로 장르별 상위 곡을 관리하는 방식도 가능하지만, 장르당 최대 두 곡만 선택하고 전체 입력 크기가 10,000 이하이므로 그룹별 정렬 방식이 구현과 검증에 더 직관적이다.

마무리

베스트앨범은 해시로 같은 장르의 데이터를 묶고, 장르 전체와 장르 내부라는 두 단계의 정렬 기준을 적용하는 문제다. 장르별 합계를 먼저 계산한 뒤 장르 순서를 정하고, 각 그룹에서 재생 수 내림차순 → 고유 번호 오름차순으로 최대 두 곡을 선택하면 조건을 빠짐없이 만족할 수 있다.

#해시#프로그래머스#난이도 3