[프로그래머스]베스트 앨범

[23] 베스트 앨범

책 구매하기

문제 정보

• 분류: 해시
• 정답률: 51%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 장르별 집계, 해시, 정렬, 상위 2곡
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제를 읽을 때 체크할 포인트

장르 전체 재생 수로 장르 우선순위를 정하고, 각 장르 안에서는 재생 수가 큰 두 곡을 고르는 문제다. 장르 집계와 곡 목록 정리를 분리해서 보면 구조가 단순해진다.

배열을 처음부터 끝까지 비교하는 쪽으로 가면 코드는 길어지고 예외도 많아진다. 이 문제는 필요한 정보를 키-값으로 압축하는 순간 풀이가 짧아진다.

풀이 흐름

1. 장르별 총 재생 수를 딕셔너리로 집계한다.
2. 장르별로 (재생 수, 고유번호)를 모아 정렬한다.
3. 총 재생 수가 큰 장르부터 순서대로 두 곡씩 answer에 넣는다.

구현할 때 놓치기 쉬운 부분

장르별 총 재생 수로 장르 순서를 정하고, 각 장르 안에서는 재생 수와 고유 번호로 다시 정렬해야 한다. 정렬 기준을 한 번에 섞어버리면 문제에서 요구한 우선순위를 놓치기 쉽다.

파이썬 정답 코드

from collections import defaultdict

def solution(genres, plays):
  # 장르별 총 재생 수를 딕셔너리로 집계한다.
  total_by_genre = defaultdict(int)
  songs_by_genre = defaultdict(list)

  # 장르별로 (재생 수, 고유번호)를 모아 정렬한다.
  for idx, (genre, play) in enumerate(zip(genres, plays)):
    total_by_genre[genre] += play
    songs_by_genre[genre].append((-play, idx))

  ordered_genres = sorted(total_by_genre, key=lambda g: total_by_genre[g], reverse=True)

  answer = []
  # 총 재생 수가 큰 장르부터 순서대로 두 곡씩 answer에 넣는다.
  for genre in ordered_genres:
    songs = sorted(songs_by_genre[genre])
    for _, idx in songs[:2]:
      answer.append(idx)

  return answer

시간 복잡도

N은 전체 곡 수이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.