주제 - “알고리즘 (해시) - 4”

부제 - 프로그래머스 코딩테스트 연습 - 파이썬

출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 베스트앨범

​ - 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.

문제 4. 베스트앨범

[문제 설명]

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

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

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

[제한사항]

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

[입출력 예]

풀이

from collections import defaultdict as dd

def solution(genres, plays):
    playOfGenre = dd(int)
    songIdAndPlay = dd(list)
    for songId, (genre,play) in enumerate(zip(genres, plays)):
        playOfGenre[genre] += play
        songIdAndPlay[genre].append((songId,play))

    playOfGenre = sorted(playOfGenre.items(), key=lambda x: x[1], reverse=True)
    answer = []
    for genre,play in playOfGenre:
        songIdAndPlay[genre].sort(key=lambda x: x[1], reverse=True)
        answer += songIdAndPlay[genre][:2]

    answer = [a[0] for a in answer]
    return answer

풀이의 포인트

베스트앨범에 수록할 노래를 선별하기 위한 기준에 집중해야 하는 문제입니다. 기준에 맞게 장르별 재생수의 합(playOfGenre), 장르 내의 재생수(songIdAndPlay), 고유번호 확인(songIdAndPlay)의 3단계를 모두 확인해야 합니다.

1) collections 모듈의 defaultdict : dictionary 형태의 object를 리턴하는 dict의 서브클래스

• value 가 없어도 dictionary 생성 가능
• 초기 생성 인자에 따라 default value 값이 달라짐

ex)

>>> a = defaultdict(int)
>>> a
defaultdict(<class 'int'>, {})

>>> b = defaultdict(list)
>>> b
defaultdict(<class 'list'>, {})

>>> c = defaultdict()
>>> c
defaultdict(None, {})

>>> a['cocojelly']
0

>>> b['cocojelly']
[]

>>> c['cocojelly']
Traceback (most recent call last):
  File "<pyshell#111>", line 1, in <module>
    c['cocojelly']
KeyError: 'cocojelly'

재생수가 높은 장르 순으로 앨범에 수록되어야 하므로, 장르별 재생 수의 합을 구해야 합니다. 그를 위해 그 값을 저장할 dictionary를 생성합니다. ‘장르’ 라는 key만 알고 아직 value를 알 수 없으므로 defaultdictionary를 이용하여 dictionary를 생성합니다.

playOfGenre는 장르별 재생 수의 합, songIdAndPlay는 장르별 곡의 재생수와 곡의 고유번호를 담을 dictionary 입니다.

>>> playOfGenre = dd(int)
	      
>>> songIdAndPlay = dd(list)

2) 내장함수 enumerate : enumerate object를 리턴하는 함수

• enumerate object는 인덱스를 포함함
• 인자로 iterable이 와야함
• for 문과 함께 많이 사용됨

ex)

>>> season = ['spring', 'summer', 'fall', 'winter']

>>> enumerate(season)
<enumerate object at 0x03C95BC0>

>>> list(enumerate(season))	      
[(0, 'spring'), (1, 'summer'), (2, 'fall'), (3, 'winter')]

>>> list(enumerate(season, start=1))
[(1, 'spring'), (2, 'summer'), (3, 'fall'), (4, 'winter')]

>>> for i in enumerate(season):
	      print (i)

(0, 'spring')
(1, 'summer')
(2, 'fall')
(3, 'winter')

생성해둔 playOfGenre, songIdAndPlay에 목적에 맞는 값을 넣기 위한 for문을 수행합니다. 풀이의 for문에서 songId는 enumerate로 인해 출력되는 인덱스 숫자, genre는 장르, play는 곡의 재생수에 해당됩니다.

playOfGenre는 int로 생성된 dictionary라 모든 key에 대한 default value가 0입니다. 따라서 곡의 재생수를 장르별로 더해가며, 각 장르별 재생수의 합(1번 조건)을 정리할 수 있습니다. 풀이의 for문에서 playOfGenre dictionary의 key인 genre에 value인 play를 더해나가는 부분이 이에 해당됩니다.

songIdAndPlay는 list로 생성된 dictionary라 모든 key에 대한 default value가 []입니다. 따라서 장르별 곡의 고유번호(3번 조건)와 재생수(2번 조건)를 묶어 list에 추가함으로써 값을 정리할 수 있습니다.

>>> genres
['classic', 'pop', 'classic', 'classic', 'pop']

>>> plays
[500, 600, 150, 800, 2500]

>>> for i in enumerate(zip(genres, plays)):
	      print (i)
	      
(0, ('classic', 500))
(1, ('pop', 600))
(2, ('classic', 150))
(3, ('classic', 800))
(4, ('pop', 2500))

>>> for songId, (genre,play) in enumerate(zip(genres, plays)):
        playOfGenre[genre] += play
        songIdAndPlay[genre].append((songId,play))
	      
>>> playOfGenre	      
defaultdict(<class 'int'>, {'classic': 1450, 'pop': 3100})

>>> songIdAndPlay	      
defaultdict(<class 'list'>, {'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]})

3) sort와 lambda를 사용하여 각 조건에 맞게 정렬

먼저 1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 를 만족하기 위해, 장르별 재생 수가 담긴 playOfGenre를 정렬합니다. sorted의 인자 각각은 아래의 의미를 가집니다.

• 정렬 대상 playOfGenre.items() : 딕셔너리 key, value의 쌍을 정렬 (playOfGenre 일 경우 결과로 장르만 정렬됨)
• 정렬 기준 key=lambda x: x[1] : item인 장르 : 재생 수 중 재생 수 를 기준으로 정렬 (x[0] 일 경우 장르를 기준으로 정렬)
• 정렬 방법 reverse=True : 큰 수부터 작은 수의 순서대로 정렬 (이 옵션이 없는 경우 작은 수부터 순서대로 정렬)

>>> playOfGenre	      
defaultdict(<class 'int'>, {'classic': 1450, 'pop': 3100})

>>> a = sorted(playOfGenre, key=lambda x:x[1], reverse=True)
>>> a
['pop', 'classic']

>>> b = sorted(playOfGenre.items(), key=lambda x:x[0])
>>> b
[('classic', 1450), ('pop', 3100)]

>>> c = sorted(playOfGenre.items(), key=lambda x:x[1])
>>> c
[('classic', 1450), ('pop', 3100)]

>>> playOfGenre = sorted(playOfGenre.items(), key=lambda x: x[1], reverse=True)
>>> playOfGenre
[('pop', 3100), ('classic', 1450)]

위의 과정을 통해 1번 조건인 많이 재생된 장르 순으로 playOfGenre 딕셔너리가 정렬됩니다.

그 다음 조건인 2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 를 만족하기 위해 반복문을 수행합니다. playOfGenre에서 순서대로 장르를 하나씩 뽑아 genre 변수에 저장하고, songIdAndPlay에서 그 장르의 리스트( songIdAndPlay[genre] )에 해당되는 곡들을 정렬합니다. 정렬 순서는 재생 수가 높은 순서대로 이므로, x[1]을 대상으로 reverse 옵션을 줘서 정렬합니다.

같은 재생 수에 해당되는 노래는 기존에 들어있던 순서처럼 고유 번호가 낮은 값이 앞에 존재합니다. 그러므로 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 조건 또한 자동적으로 만족합니다.

>>> songIdAndPlay	      
defaultdict(<class 'list'>, {'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]})

>>> for genre,play in playOfGenre:
        songIdAndPlay[genre].sort(key=lambda x: x[1], reverse=True)
        
>>> songIdAndPlay
defaultdict(<class 'list'>, {'classic': [(3, 800), (0, 500), (2, 150)], 'pop': [(4, 2500), (1, 600)]})

장르 별로 가장 많이 재생된 노래를 두 개씩 모으는 것이 최종 목적이었으므로, 정렬된 songIdAndPlay에서 장르별로 앞에서 2곡을 뽑아내어 (장르에 속한 곡이 하나라면 하나의 곡만 선택됨) 노래의 고유번호만을 리턴합니다.

>>> a = [0, 1, 2, 3]
>>> a[:2]
[0, 1]

>>> b = [0]
>>> b[:2]
[0]

>>> songIdAndPlay
defaultdict(<class 'list'>, {'classic': [(3, 800), (0, 500), (2, 150)], 'pop': [(4, 2500), (1, 600)]})

>>> answer = []

>>> for genre,play in playOfGenre:
        answer += songIdAndPlay[genre][:2]
        
>>> answer
[(4, 2500), (1, 600), (3, 800), (0, 500)]

>>> answer = [a[0] for a in answer]
>>> answer
[4, 1, 3, 0]

이전 - [프로그래머스 - 코딩테스트 연습] 해시 (3)