프로그래머스 - 해시 - 베스트앨범 / 장르별 재생수 반환 문제

문제 설명

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

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

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

 

제한사항

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

입출력 예

genresplaysreturn

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

 

접근방법

1. 장르별로 K : V 구조로 리스트에 저장한다.  즉, Dictionary 형태로 만든다.

예:  #1. {'classic' : [[0, 500], [2, 150], [3, 800]], 'pop': [[1, 600], [4, 2500]]}

설명: 클래식은 0번째 Key에 500이란 Value를 가지고 2번쨰 Key에 150, 3번째 Key에 800이라는 Value를 갖습니다.

팝은 1번째 Key에 600, 4번째 Key에 2500이라는 Value를 갖습니다.

 

2. 어떠한 장르가 가장 많이 듣는지 알기 위해서 1번 과정을 거친 Dictionary 형태에서 장르별로 Value만 다 더한다.

예: #2. {'classic': 1450, 'pop': 3100}

 

3. 2번으로 나온 Dictionary 구조에서 정렬(Sorted) 함수를 이용해서 하는데, 단 Value를 가지고 진행한다.

Sorted(정렬할 대상, 정렬 기준이 될 Key, 정렬 방법)

여기서 두 번째 인자로 들어갈 정렬 기준이 될 Key부분에서는 lambda를 활용하여 어떤 값이 정렬의 기준이 될 지 정한다.

#3. {'pop': 3100, 'classic': 1450}

#4. [[0, 500], [2, 150], [3, 800]] , [[1, 600], [4, 2500]]

4. 3번으로 Dictionary가 정렬된 상태에서 [예: ({'pop': 3100, 'classic': 1450})] pop에 대한 1번의 Dictionary에서 Key만 가지고 오고, classic에 대한 1번의 Dictionary에서 Key만 가지고 온다. (붉은색으로 표기된 Dictionary) 

단, Key를 바로 가져오는 것이 아니라 1번 Dictionary에서 각 장르별 Value로 선 정렬한 뒤에 Key를 가져와야 한다.

여기서도 3번과 마찬가지로 lambda를 이용하여 sorted하면 된다.

 

 

코드설명

1번에 대한 내용

변수: 장르에 대한 K : V 구조로 만들기 위한 Dictionary: genre_play_list_dict

genre_array : 장르에 대한 배열

play_array : 재생횟수에 대한 배열

genre_play_list_dict = {}

n = len(genre_array)

for i in range(n) :

    genre = genre_array[i]

    play = play_array[i]

    if genre not in genre_play_list_dict:  # 딕셔너리에 추가할 장르가 딕셔너리에 있는지를 먼저 확인

        genre_play_list_dict[genre] = [ [ i, play] ]

    else:

        genre_play_list_dict[genre].append([ i, play ] )

 

# 1.에 대한 내용과 비슷한 구조로 넣어야 하기 때문에 배열 형태로 입력한 것이고, 딕셔너리 내에 원래 장르가 

있을 경우, 해당 장르의 다른 Key (== i), Value(==play)인 배열형태로 값을 넣어줘야한다.

 

다음은 장르별로 재생 횟수를 더하는 방법이다.

변수: genre_total_list_dict: 장르별 합계를 나타내는 딕셔너리

 

for i in range(n):

    genre = genre_array[i]

    play = play_array[i]

    if genre not in genre_total_list_dict:

         genre_total_list_dict[genre] = play

    else:

         genre_total_list_dict[genre] += play

 

장르가 genre_total_list_dict에 없을 경우 아직 추가되지 않은 상태이기에 해당 재생수를 그대로 넣는다.

그렇지만 이미 딕셔너리에 존재하는 장르라면, 해당 장르를 Key로 하여 재생수를 더해준다.

이렇게 작업해서 나온 genre_total_list_dict 결과는 #2. 와 같을 것이다.

 

여기서 장르별 합계(Value)를 가지고 정렬을 해야한다.   앞서 설명한 sorted 함수를 이용할 것이다.

아래 참조링크를 참고하여 sorted 내장함수 설명을 추가로 확인하고 오면 더 좋을 것이다.

#3. sorted_total_list_dict = sorted(genre_total_list_dict.items(), key=lambda item: item[1], reverse= True)

 

이렇게 정리된 딕셔너리에 대해서 반복을 돌리되, 딕셔너리의 키인 장르에 대해서 반복을 돌리되, 

처음 #1. 과 같이 #3. 으로 정렬한 장르를 Key로하여 접근하고, 거기서 #4. 나온 값(K : V) 을 Value로 다시 정렬하여

Key를 따로 리스트에 추가하면 된다.

 

for genre, play in sorted_total_list_dict: # '장르', '관객수'
      sorted_genre_play_list = (sorted(genre_play_list_dict[genre], key=lambda item: item[1], reverse=True)) # key = lambda item: item[1]
# 정렬할 때 key로는 item내 첫 번째 인자 -> 값으로 가겠다.
for inx in range(len(sorted_genre_play_list)):
     if inx > 1:
          break
     result.append(sorted_genre_play_list[inx][0]) # Key를 뽑아와야하므로 

 

 

전체코드

genres = ["classic", "pop", "classic", "classic", "pop", "balad"]
plays = [500, 600, 150, 800, 2500,700]


def get_melon_best_album(genre_array, play_array):
genre_play_list_dict = {}
genre_total_list_dict = {}
n = len(genre_array)
for i in range(n):
      genre = genre_array[i] # 장르 순서대로 가져오기
      play = play_array[i] # 장르 순서에 맞게 관객수 가져오기
      if genre not in genre_play_list_dict: # 장르가 장르랑 관객수 같이 리스트업 하는 딕셔너리에 있는지 파악
           genre_play_list_dict[genre] = [[i, play]] # 없을 경우 그냥 넣어주기
      else: # 만약에 있다면 append로 추가해주기 (i가 덮어 씌워지는 이슈를 막기 위함)
          genre_play_list_dict[genre].append([i, play])


# print(genre_play_list_dict)

# 합계를 나타내는 dict
for i in range(n):
    genre = genre_array[i]
    play = play_array[i]
    if genre not in genre_total_list_dict: # 장르의 합계를 관리하는 딕셔너리에 장르가 없을 경우
        genre_total_list_dict[genre] = play # 해당 장르에 대해서 관객수만 더해줄 것
    else:
       genre_total_list_dict[genre] += play # 기존 탐색했던 딕셔너리 내 더해야 할 장르가 존재할 경우 관객수를 거기에다가 추가로 더해줄 것

# print(genre_total_list_dict)

# 클래식과 팝 중에 더 합계가 높은 것 먼저 가지고 오기
# 그 장르 중 관객수가 더 많은 키를 배열에 넣기

sorted_total_list_dict = sorted(genre_total_list_dict.items(), key=lambda item: item[1], reverse=True)
# print(sorted_total_list_dict)
result = []

for genre, play in sorted_total_list_dict: # '장르', '관객수'
     sorted_genre_play_list = (sorted(genre_play_list_dict[genre], key=lambda item: item[1], reverse=True)) # key = lambda item: item[1]
# 정렬할 때 key로는 item내 첫 번째 인자 -> 값으로 가겠다.
    for inx in range(len(sorted_genre_play_list)):
         if inx > 1:
            break
        result.append(sorted_genre_play_list[inx][0])

return result

print(get_melon_best_album(genres, plays)) # 결과로 [4, 1, 3, 0] 가 와야 합니다!

 

 

참조: https://programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

참조: https://docs.python.org/ko/3/howto/sorting.html

정렬 HOW TO — Python 3.9.5 문서