프로그래머스 Lv.3 | Python | 베스트앨범

1. 문제 정보

프로그래머스

 

• 난이도: Lv.3

---

2. 문제 설명

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

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

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

 

제한 조건

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

---

3. 접근 기준

이 문제는 단순 정렬 한 번으로 끝나는 문제가 아니다.
먼저 장르별 총 재생 수를 구해야 하고, 그 다음 각 장르 안에서 노래를 다시 정렬해야 한다.

즉, 다음 순서로 접근해야 한다.

1. 장르별 총 재생 수 집계
2. 총 재생 수 기준으로 장르 정렬
3. 각 장르 안에서 노래를 정렬
4. 장르별 상위 2곡 선택

핵심은 노래 하나만 보는 것이 아니라, 장르 단위 집계와 장르 내부 정렬을 분리해서 처리해야 한다는 점이다.

---

4. 사용한 패턴 / 알고리즘

해시(Dictionary)

• 장르별 총 재생 수 저장
• 장르별 노래 목록 저장

정렬(Sorting)

• 장르별 총 재생 수 기준 정렬
• 장르 내부에서 재생 수 내림차순, 고유번호 오름차순 정렬

즉, 해시로 그룹화하고 정렬로 우선순위를 적용하는 문제라고 볼 수 있다.

---

5. 핵심 아이디어

• 이 문제의 핵심은 데이터를 두 단계로 나눠서 관리하는 것이다.
• 첫 번째는 장르별 총 재생 수다. 이 값은 어떤 장르를 먼저 베스트앨범에 넣을지를 결정한다.
• 두 번째는 장르별 노래 목록이다. 이 목록은 해당 장르 안에서 어떤 노래를 먼저 선택할지를 결정한다.

예를 들어:  

• genre_total[장르]
  → 해당 장르 전체 재생 수
• genre_songs[장르]
  → (재생 수, 고유번호) 목록

이렇게 나누면 문제 조건을 그대로 코드에 옮길 수 있다.

• 특히 장르 안에서는 재생 수가 큰 순서, 같다면 고유번호가 작은 순서로 정렬해야 하므로

key=lambda x: (-x[0], x[1])

---

6. 풀이 코드

초기코드

def solution(genres, plays):
    answer = []
    _new = list()
    _dict = {}
    for i in range(len(genres)):
        _new.append([genres[i],plays[i],i])
    _new.sort(key=lambda x: (-x[1],x[2]))
    
    for i in range(len(_new)):
        _dict[_new[i][0]]=_dict.get(_new[i][0],0) + _new[i][1]
    
    _dict=sorted(_dict.items(), key=lambda x:x[1], reverse=True)
    
    for key,value in _dict:
        cnt=0
        for i in range(len(_new)):
            if key == _new[i][0]:
                if cnt==2:break
                answer.append(_new[i][2])
                cnt+=1
    return answer​

 

최적화 코드

def solution(genres, plays):
    answer = []
    genre_total = {}
    genre_songs = {}

    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_total[genre] = genre_total.get(genre, 0) + play
        genre_songs.setdefault(genre, []).append((play, i))

    sorted_genres = sorted(genre_total, key=lambda x: genre_total[x], reverse=True)

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

    return answer​

---

7. 초기 코드 vs 최적화 코드 비교

1. 초기 코드

• 전체 데이터를 _new 리스트 하나로 관리
• 이후 장르별 총합 계산
• 다시 장르별로 전체 리스트를 반복 탐색

→ 특징

• 같은 데이터를 여러 번 순회
• 흐름이 길고 조건이 뒤섞임
• 시간 복잡도 증가 (불필요한 반복)

2. 최적화 코드

• 처음부터 데이터를 분리
  • genre_total → 장르 총합
  • genre_songs → 장르별 노래 목록
• 이후는 정렬 + 선택만 수행

→ 특징

• 한 번 순회로 구조 완성
• 로직이 단계별로 분리됨
• 불필요한 반복 제거

핵심 차이

• 초기 코드: 전체 기준 → 나중에 분리
• 최적화 코드: 처음부터 기준별 분리

---

8. 핵심 로직 요약

• 장르별 총 재생 수를 딕셔너리에 저장한다.
• 장르별 노래 목록도 따로 저장한다.
• 장르를 총 재생 수 기준으로 정렬한다.
• 각 장르 내부 노래를 재생 수 내림차순, 고유 번호 오름차순으로 정렬한다.
• 상위 2곡의 고유 번호만 결과에 담는다.

결국, “장르별 그룹화 + 장르 우선순위 정렬 + 장르 내부 상위 2곡 선택” 이 흐름이 전체 로직의 핵심이다.

---

9. 정리

이 문제는 조건이 많아 보여서 복잡해 보이지만, 실제로는 데이터를 어떻게 나눠서 저장할지 결정하면 훨씬 쉬워진다.

• 장르별 총합을 구한다
• 장르별 노래를 묶는다
• 장르 순서를 정한다
• 각 장르에서 2곡만 뽑는다

이 순서만 유지하면 안정적으로 풀 수 있다.

• 처음 작성한 코드도 정답은 만들 수 있다.  다만 전체 리스트를 기준으로 다시 장르를 반복 탐색하는 방식이라, 조건이 늘어날수록 흐름이 길어진다.
• 반대로 개선한 코드는  문제의 기준인 장르별 총합과 장르별 노래 목록을 처음부터 분리해서 관리하므로 로직이 더 명확하고 읽기도 쉽다.

이 문제를 통해 익혀둘 포인트는 다음과 같다.

• 여러 기준이 섞인 정렬 문제는 먼저 그룹화부터 생각하기
• 딕셔너리를 이용해 기준별 데이터를 분리하면 로직이 단순해짐
• 정렬 기준이 여러 개일 때는 key=lambda x: (-기준1, 기준2) 형태를 떠올리기