[프로그래머스] 베스트앨범 - Level 3 (Python)

📌 문제 정보

베스트앨범 Level 3

플랫폼

프로그래머스

유형

해시, 정렬

언어

Python 3

풀이 시간

약 50분

풀이 날짜

2026.05.02

문제 링크

바로가기 ↗

---

🧩 문제 요약

genres(장르)와 plays(재생 횟수) 배열을 받아, 각 곡의 장르별 정보를 바탕으로 베스트 앨범에 들어갈 노래를 선정해 반환하는 문제

명령 조건:

• 가장 많이 재생된 총 재생 횟수가 많은 장르를 먼저 수록
• 한 장르 안에서는 재생 횟수가 많은 노래를 먼저 수록
• 장르 내에서는 최대 2곡까지만 수록

입력 조건:

• genres[i], plays[i] 는 i번째 곡의 장르, 재생 횟수
• genres와 plays의 길이는 같음

출력 조건:

• 베스트 앨범에 들어갈 노래의 인덱스를 담은 배열 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

dict 하나에 장르별로 **총 재생 횟수(total)**와 곡 인덱스별 재생 횟수를 같이 저장하기로 했다.

d[g] = {"total": 0}
d[g]["total"] += plays[i]
d[g][i] = plays[i]

key에 문자열("total")과 숫자(곡 인덱스)를 섞어 쓰는 구조라, "total"이 일반 곡 인덱스로 오인되지 않게 정렬할 때마다 if k != "total"로 걸러내야 했다.

2단계 - 막혔던 부분

• d["classic"]["total"] = 1450 처럼 중첩 dict에 바로 값을 넣으려다 d["classic"] 자체가 없어 KeyError가 발생했다. → 바깥 key부터 먼저 생성해야 한다는 걸 깨달았다.
• += 연산은 d[g]["total"] = d[g]["total"] + plays[i] 처럼 오른쪽 값을 먼저 읽기 때문에, total을 0으로 미리 초기화해두지 않으면 에러가 났다.
• sorted(d, ...) 결과를 변수에 담지 않고 그냥 호출만 해서, 실제로는 아무 정렬도 반영되지 않은 채로 다음 로직을 짤 뻔했다. → sorted()는 원본을 바꾸지 않고 새 리스트를 반환만 한다는 점을 다시 확인했다.

3단계 - 해결 실마리

장르별 총 재생 횟수로 1차 정렬(sorted_genres), 각 장르 안에서 곡 인덱스를 재생 횟수 기준으로 2차 정렬(sorted_songs) 후 상위 2개만 추출하는 2단계 정렬 구조로 완성했다.

핵심 아이디어:

• dict의 value를 다시 dict로 만들어 {"total": 0, 곡인덱스: 재생수} 구조로 관리
• sorted(..., key=lambda x: d[x]["total"], reverse=True)로 장르를 총 재생 횟수 내림차순 정렬
• 장르 내부는 "total"을 제외한 뒤 재생 횟수 기준 내림차순 정렬, enumerate로 상위 2개까지만 선택

---

✅ 최종 풀이 코드

def solution(genres, plays):
    answer = []
    d = {}
    for i, g in enumerate(genres):
        if g not in d:
            d[g] = {"total": 0}
        d[g]["total"] += plays[i]
        d[g][i] = plays[i]

    sorted_genres = sorted(d, key=lambda x: d[x]["total"], reverse=True)

    for g in sorted_genres:
        sorted_songs = sorted(
            {k: v for k, v in d[g].items() if k != "total"}.items(),
            key=lambda x: x[1],
            reverse=True,
        )

        for idx, (song_idx, _) in enumerate(sorted_songs):
            if idx == 2:
                break
            answer.append(song_idx)

    return answer

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(n log n)	dict 생성 O(n) + 장르 정렬 O(g log g) + 장르별 곡 정렬 합 O(n log n)
공간 복잡도	O(n)	곡 수만큼 dict, 정렬용 리스트, answer 배열이 비례해서 생성됨

장르 수(g)는 곡 수(n)보다 항상 작거나 같으므로, 전체 시간 복잡도를 지배하는 항은 곡 단위 정렬인 O(n log n)이다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	d["classic"]["total"] = 1450 처럼 바깥 key 없이 바로 중첩 접근 → KeyError	d[g] = {"total": 0} 으로 바깥 key부터 먼저 생성
2차	sorted(d, key=..., reverse=True) 결과를 변수에 담지 않고 그냥 호출 → 정렬이 반영 안 됨	sorted_genres = sorted(...) 로 반환값을 변수에 저장
3차	통과 ✅	-

---

🔄 다른 풀이 방법

dict 2개로 역할 분리 (총재생수 / 곡목록)

def solution(genres, plays):
    answer = []
    dic1 = {}
    dic2 = {}

    for i, (g, p) in enumerate(zip(genres, plays)):
        if g not in dic1:
            dic1[g] = [(i, p)]
        else:
            dic1[g].append((i, p))

        if g not in dic2:
            dic2[g] = p
        else:
            dic2[g] += p

    for (k, v) in sorted(dic2.items(), key=lambda x: x[1], reverse=True):
        for (i, p) in sorted(dic1[k], key=lambda x: x[1], reverse=True)[:2]:
            answer.append(i)

    return answer

내 풀이 vs 이 풀이 비교:

• 내 풀이: dict 하나에 {"total": ..., 곡인덱스: 재생수} 형태로 합쳐서 관리, enumerate + break로 상위 2개 선택
• 이 풀이: "총 재생 횟수용 dict"와 "곡 목록용 dict"를 처음부터 분리, zip()으로 genres/plays를 한 번에 순회, [:2] 슬라이싱으로 상위 2개를 바로 추출
• 역할을 분리하니 "total"을 걸러내는 if k != "total" 같은 예외 처리가 필요 없어져서 더 간결함

tie-break까지 고려한 정렬

genres_dict = {}
play_dict = {}

for i in range(len(genres)):
    genre = genres[i]
    play = plays[i]
    if genre not in genres_dict:
        genres_dict[genre] = []
        play_dict[genre] = 0
    genres_dict[genre].append((i, play))
    play_dict[genre] += play

sorted_genres = sorted(play_dict.items(), key=lambda x: x[1], reverse=True)

answer = []
for genre, _ in sorted_genres:
    sorted_songs = sorted(genres_dict[genre], key=lambda x: (-x[1], x[0]))
    answer.extend([idx for idx, _ in sorted_songs[:2]])

return answer

reverse=True vs key=lambda x: (-x[1], x[0]) 비교:

• 내 풀이는 재생 횟수만 기준으로 reverse=True 정렬 → 재생 횟수가 같을 때 어떤 곡이 먼저 올지 보장 안 함
• tie-break까지 고려한 정렬 풀이는 -x[1](재생 횟수 내림차순), x[0](인덱스 오름차순)을 튜플로 묶어 재생 횟수가 같을 경우 인덱스가 작은 곡을 우선하도록 tie-break 처리
• reverse=True는 기준 전체를 한 방향으로만 뒤집지만, - 부호는 기준별로 정렬 방향을 따로 줄 수 있다는 차이가 있음

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: dict의 value로 다시 dict를 넣을 수 있고, d[g][key] = value처럼 바로 값을 넣으려면 바깥 key가 먼저 존재해야 한다. +=는 기존 값을 먼저 읽기 때문에 초기값 설정이 선행되어야 한다.
• ✏️ 새로 알게 된 것: sorted()는 원본을 바꾸지 않고 새 리스트만 반환하므로 반드시 변수에 담아야 하며, key=lambda x: -x[1]처럼 부호를 반전시키면 reverse=True 없이도 내림차순 정렬이 가능하고, 여러 기준을 각각 다른 방향으로 정렬하고 싶을 때 유용하다.
• ⚠️ 실수했던 점: sorted(d, key=..., reverse=True)를 변수에 담지 않고 그냥 호출만 해서 정렬 결과가 사라질 뻔했다. sorted()와 .sort()의 차이(반환 vs 원본 변경)를 명확히 구분하지 못했던 게 원인이었다.
• 💬 한 줄 요약: 중첩 dict를 쓸 땐 바깥 key부터 순서대로 만들고, 정렬 기준이 여러 개일 땐 reverse=True 대신 (-x[1], x[0]) 같은 부호 반전 튜플을 활용하자!