1일 1커밋 !

1일 1PS 79일차!

📚 문제

[Level 3] - 베스트앨범

💡 풀이 과정

  • 2024 팀 네이버 코딩테스트가 내일 모레이기에 프로그래머스에서 연습하고자 한다.
    • 해당 연습에서는 디버깅 툴 없이 print 와 주석을 최대한 활용한다.


  • 문제는 각 장르별로 노래 재생 횟수를 카운팅하고
  • 가장 많이 들은 장르 순서대로 가장 많이 재생된 노래를 출력하는 문제이다.
  1. 각 장르별 노래 재생 횟수 총 합
  2. 각 장르별 최다 재생 곡 2개
  • 위 두 가지 처리가 필요하다.


  • 1번은 쉽게 처리할 수 있다.
  • 문자열이므로 딕셔너리를 사용해 총합 카운팅을 기록할 dic_total 을 생성했다.
  • 처음 들어오는 장르라면 0 으로 초기화해주고 이후에는 계속해서 더해준다.
  • 모든 곡이 정리되면 이제 정렬을 해야하는데,
    • genre_list = sorted(dic_total, key= lambda x: dic_total[x], reverse = True)
    • dic_total 의 값들을 정렬해줄 것이며 dic_total[“장르”] 의 값을 기준으로 내림차순 정렬한다.
    • 어렵다면 maxHeap 을 사용해서 (total, “genre”) 로 하나씩 pop 해도 될 것 같지만
      • 매번 더해줄때마다 pop 후 push, 마지막 모든 요소 pop 등이 매우 비효율적일 것이다.
  • 이제 속한 노래가 많이 재생된 장르 순서대로 정렬되었으니 2번으로 넘어가자.


  • 2번을 진행하기 위해서는 각 장르별로 재생 노래 수를 정렬해야한다.
  • 그렇다면 input 이 들어올 때 미리 각 장르별로 maxHeap 을 생성하고 (plays, index) 를 미리 저장해놓아야한다.
  • 이를 위한 dic_plays 를 놓고 “genre” : [minHeap] 을 구성한다.


  • 이제 genre_list 순서대로 dic_plays[genre] 를 접근하면서 최다 재생 노래를 answer 에 append 해준다.

📌포인트

  • heapq
    • heapq 의 peek 를 구하기 위해서는 그냥 heapq[0] 을 조회하면 되었다.
    • 따라서 heapq[1] 로 두 번째 수를 접근할 수 있을 줄 알았다.
    • 자료구조를 보면 알겠지만 tree 구조인 heapq 에서는 [0] 만 최대, 최소값이 유지된다.
    • 따라서 heappop() 으로 1번째 곡을 조회하고 이후에 heapq[0] 으로 두 번째 곡을 조회했다.
  • 문제 조건을 잘 읽어 TC 를 만족해야한다.
    • 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
      • 이는 파이썬에서는 기본적으로 최소힙이며 (-1 * plays, index) 이므로 둘 다 작은 값을 우선 시 한다.
    • 모든 장르는 재생된 횟수가 다릅니다.
      • dic_total 이 겹칠 경우는 고려하지 않아도 된다.
    • 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
      • 이것을 처리해주지 않았다면 오답이다.
      • 이를 위해 heappop 이후 요소가 남아있는 지 확인하고 answer 에 추가해야한다.

  • 위 조건들을 자체 테스트케이스에 추가해서 코드를 확인하자!!

  • defaultdict
    • defualtdict 를 사용해서 not in dic .. 구문을 삭제할 수도 있지만
    • 개인적으로 import 하지 않고 푸는 것을 선호해서 그냥 조건을 생성했다.

💻 코드

import heapq

def solution(genres, plays):
    N = len(plays)
    answer = []
    dic_total = {}
    dic_plays = {}
    
    for i in range(N):
        # 새로운 장르라면 dic 에 추가한다.
        if genres[i] not in dic_total:
            dic_total[genres[i]] = 0
            dic_plays[genres[i]] = []
            
        # Total 에는 장르의 전체 재생 횟수를 추가한다.
        dic_total[genres[i]] += plays[i]
        # Plays 에는 max Heap 에서 (재생 횟수, 고유 번호) 를 저장한다.
        # 이때 재생횟수가 높을 수록, 고유 번호가 낮을 수록 우선순위가 높다.
        heapq.heappush(dic_plays[genres[i]], (-1 * plays[i], i))
        
    print(dic_total)
    print(dic_plays)
        
    genre_list = sorted(dic_total, key= lambda x: dic_total[x], reverse = True)
    for genre in genre_list:
        # 장르에서 가장 많이 재생된 곡
        answer.append(heapq.heappop(dic_plays[genre])[1])
        
        # 장르에 속한 곡이 하나라면..!!
        if dic_plays[genre]:
            # 장르에서 두 번째로 많이 재생된 곡
            answer.append(dic_plays[genre][0][1])

    
    return answer

업데이트:

댓글남기기

참고