설명

프로그래머스의 베스트 앨범 문제다.

음악 스트리밍 사이트에서 장르별로 가장 많이 재생된 곡을 두 곡씩 뽑아서 출시하려 할 때 이를 구하는 알고리즘을 작성하는 문제다. 단순히 두 곡씩 뽑는건 아니고 다음과 같은 제한이 있다.

• 장르 순서는 해당 장르 노래의 재생 횟수의 합(내림차순)으로 정한다.
• 각 장르에서 두 곡씩 뽑을 때는 재생 횟수(내림차순)대로 선택한다.
• 재생 횟수가 동일하다면 고유 번호가 더 빠른 노래를 먼저 선택한다.

문제를 제대로 안 읽어서 초반에 조금 헷갈린 점이 장르 순서는 해당 장르 노래의 재생 횟수의 합으로 정하지만 한 장르에서 두 곡을 뽑지 전체 장르에서 두 장르만 뽑는 것은 아니다.

풀이

단순 정렬

재생 횟수의 합으로 장르 순서를 선택해야 하기 때문에 각 장르별 노래의 재생 횟수를 전부 탐색해서 합한 순서대로 제일 많이 재생된 두 곡씩 선택해야 한다.

초반에 간과했던 점은 노래의 재생 횟수가 동일하다면 고유 번호 순서대로 선택해야 한다는 것이다.

>>> a=(1, 2, 3, 3)
>>> b=(1, 2, 3, 4)
>>> a > b
False
>>> a < b
True
>>>

파이썬에서 튜플이나 리스트를 비교할 때는 첫 번째 요소가 동일할 경우 자동적으로 다음 요소까지 비교한다. 그래서 각 노래의 재생 횟수를 음수로 하고 고유 번호와 함께 정렬해주면 재생 횟수가 동일할 경우 더 빠른 고유 번호의 노래를 먼저 참조할 수 있다.

이를 기반으로 구현한 코드는 다음과 같다.

import collections


def solution(genres, plays):
    # 각 장르의 각 노래의 재생 횟수를 담을 사전.
    musics = collections.defaultdict(list)
    
    # 사전에 각 장르별 노래의 재생 횟수를 등록.
    for index, genre in enumerate(genres):
        musics[genre].append((plays[index], index))
        
    # 장르별 노래들의 재생 횟수의 합을 계산하여 (합, 장르)의 리스트로 변환.    
    played_genres = [(sum([played_count[0] for played_count in played_counts]), genre) for genre, played_counts in musics.items()]
    # 1차적으로 장르들을 재생 횟수가 적은 순서대로 정렬.
    played_genres.sort()
    # 역순으로 재생 횟수가 많은 순서의 장르 이름을 리스트로 생성.
    best_played_genre = [played_genre[1] for played_genre in played_genres][::-1]
        
    answer = []
    # 사전에서 재생 횟수가 많은 장르 순서대로 참조, 두 곡씩 추출.
    for genre in best_played_genre:
        # 재생 횟수와 인덱스의 음수를 튜플로 하여 정렬.
        # 이 경우 재생 횟수가 같은 노래들이 인덱스의 역순으로 정렬됨.
        # 이는 코드에서 리스트의 마지막 요소를 제거하는 pop 연산을 사용하기 위함.
        plays = [(play, -index) for (play, index) in musics[genre]]
        plays.sort()
        
        # 리스트의 마지막 요소, 즉 재생 횟수가 가장 많은 노래를 추출.
        # 두 번째 우선순위로 인덱스가 더 빠른(음수이므로) 노래를 추출.
        answer.append(-plays.pop()[1])
        # 노래가 하나만 존재할 수 있으므로 예외처리.
        if plays:
            answer.append(-plays.pop()[1])
    
    return answer

하지만 정렬 메서드를 자주 사용하게 되는 것 같다.

heapq 사용

어차피 정렬할거라면 우선순위 큐를 사용할 수도 있지 않을까? 파이썬의 heapq 모듈을 이용해서 우선순위 큐로 더 간단하게 풀 수 있는데 아마 이 방법이 문제에서 의도한 방법이 아닐까 생각한다.

import collections
import heapq


def solution(genres, plays):
    # 음악 정보를 담는 사전 자료형.
    musics = collections.defaultdict(list)
    
    # 음수 재생 횟수와 인덱스를 튜플로 같이 사전에 삽입.
    # heapq 모듈은 항상 오름차순이기 때문에 재생 횟수를 음수화.
    for index, genre in enumerate(genres):
        heapq.heappush(musics[genre], (-plays[index], index))
    
    # 음수 재생 횟수의 합이기 때문에 역순으로 정렬.
    played_genres = [(sum([-played_count[0] for played_count in played_counts]), genre) for genre, played_counts in musics.items()]
    played_genres.sort(reverse=True)
    
    answer = []
    # 간단하게 heappop 메서드로 가장 많이 재생된(또는 인덱스가 빠른) 노래 추출.
    for _, genre in played_genres:        
        answer.append(heapq.heappop(musics[genre])[1])
        if musics[genre]:
            answer.append(heapq.heappop(musics[genre])[1])
    
    return answer

후기

파이썬의 여러 모듈과 언어 자체의 특성을 활용하면 활용할수록 문제풀이가 한결 편해지는 것 같다. Counter 모듈도 응용할 수 있는곳에 바로바로 사용할 수 있도록 연습해봐야겠다.