[Python] 프로그래머스 - 베스트앨범 (해시)

문제 설명

📃 문제 링크

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

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

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

제한사항

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

문제 풀이

처음에는 다음과 같이 풀었다.

def solution(genres, plays):
    answer = []
    _hash = {}
    for i in range(len(genres)):
        if genres[i] in _hash:
            _hash[genres[i]] += plays[i]
        else:
            _hash[genres[i]] = plays[i]
    
    while len(_hash) > 0:
        genre_max = max(_hash.keys(),key=(lambda k:_hash[k]))
        del(_hash[genre_max])
        
        second = largest = 0
        for i in range(len(genres)):
            if genres[i] == genre_max:
                if plays[i] >= largest:
                    second = largest
                    largest = plays[i]
                elif second < plays[i] < largest:
                    second = plays[i]
                    
        answer.append(plays.index(largest))
        if second != 0:
            answer.append(plays.index(second))
            
    return answer

재생횟수가 많은 장르를 먼저 수록하므로, _hash 라는 이름의 dict 타입 변수를 사용해 {'classic': 1450, 'pop': 3100} 처럼 나올 수 있도록 했다. _hash에서 가장 재생 횟수가 많은 장르를 찾아 장르명을 저장하고, 선택된 장르는 _hash에서 삭제했다. 그 후 genres 배열과 plays 배열을 탐색해 선택된 장르에서 재생횟수가 가장 많은 노래와 두 번째로 많은 노래를 찾아 answer에 index를 넣어주었다.

이 방식으로 풀었을 때는 테스트 케이스 중에 2개가 실패했다. 문제를 다시 꼼꼼히 읽어보니 조건 중 놓친 것이 있었다... 바로 모든 장르는 재생된 횟수가 다릅니다.

나는 이 말이 각 노래의 재생 횟수가 모두 다르다는 말인 줄 알았는데, 장르별 총 재생 횟수만 다르고 노래별 재생 횟수는 같을 수도 있다는 것이었다. 재생 횟수가 같은 테스트 케이스를 추가해보니 인덱스가 무조건 그 값의 첫번째 인덱스로 들어가서 올바른 답이 나오지 않았다.

그래서 재생 횟수와 고유 번호를 Tuple로 묶어 해시를 만들고 기존 방법대로 탐색해보려 했는데, 점차 하드 코딩이 되어감을 느꼈다... 첫 번째, 두 번째로 큰 수를 찾는 것보다 정렬해서 푸는 것이 훨씬 깔끔할 것 같아 sorted함수를 사용해서 다시 풀었다.

알게 된 것

dictionary에 값을 넣을 때, 아래 코드처럼 해당 이름의 키가 있는지 없는지 항상 검사했었다.

dict = {}
if key in dict:
    dict[key] += temp
else:
    dict[key] = temp

이렇게 할 필요 없이, 파이썬의 내장 모듈인 collections의 defaultdict 클래스를 사용해 기본값을 넣어주면 된다. defaultdict 클래스의 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다.

from collections import defaultdict

dict = defaultdict(int)
dict[key] += temp

defaultdict 클래스의 생성자로 int 함수를 넘겨주었고, int()는 0을 리턴한다. 람다 함수를 활용해 lambda: 0을 넘겨주어도 동일하게 작동한다.

소스 코드