[Python] 해시_베스트앨범(3단계)

EunBi Na·2022년 4월 12일

[Python] 프로그래머스_코딩테스트 고득점 Kit

목록 보기

23/60

문제 설명

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

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

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

제한사항

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

입출력 예

genres	plays	return
["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

기본적으로 해시 알고리즘이 이용되는 문제다. 파이썬에서 해시 알고리즘은 딕셔너리를 사용한다. 키-값의 일대일 매핑이 이루어지기 때문이다.

[장르, 재생횟수, 인덱스(고유번호)]를 형식으로 하는 리스트 생성
조건1. "속한 노래가 가장 많이 재생된 장르를 먼저 수록"을 만족시키기 위해서, 장르를 KEY로 하는 딕셔너리를 생성하여 VALUE에 KEY와 매칭되는 재생횟수를 저장
조건2.3. "재생 횟수가 많을수록, 같다면 고유번호가 낮을수록 먼저 수록"을 만족시키기 위해서, 1에서 생성한 리스트를 재생횟수 기준 내림차순, 고유번호 기준 오름차순 정렬
2에서 생성한 딕셔너리 KEY 순서대로 정렬한 리스트를 탐색하며 최대 count 2까지의 고유번호를 수록

def solution(genres, plays):
    answer = []
    temp = []
    total_genre_d = {}

    temp = [[genres[i], plays[i], i] for i in range(len(genres))]   # [장르, 재생횟수, 고유 번호] 리스트
    temp = sorted(temp, key=lambda x: (x[0], -x[1], x[2]))  # 많이 재생될수록, 같다면 고유번호가 낮을수록

    for g in temp:  # {장르 : 총 재생횟수} 딕셔너리 생성
        if g[0] not in total_genre_d:
            total_genre_d[g[0]] = g[1]
        else:
            total_genre_d[g[0]] += g[1]
    
    total_genre_d = sorted(total_genre_d.items(), key = lambda x: -x[1])    # 재생횟수가 많은 순서로 장르 정렬
    
    for i in total_genre_d: # 같은 장르 내에서는 최대 2곡까지 조건대로 수록
        count = 0
        for j in temp:
            if i[0] == j[0]:
                count += 1
                if count > 2:
                    break
                else:
                    answer.append(j[2])

    return answer

문제풀이2

내 풀이랑 로직은 비슷한데 이 사람은 딕셔너리를 생성할 때 아예 2개를 만들어서 풀이했다. 나는 딕셔너리 1개의 KEY와 리스트의 요소를 비교했는데 딕셔너리 2개를 만들어서 더 코드가 간결해보이는 것 같다.

def solution(genres, plays):
    answer = []

    dic1 = {}
    dic2 = {}

    for i, (g, p) in enumerate(zip(genres, plays)):
        if g not in dic1:
            dic1[g] = [(i, p)]
        else:
            dic1[g].append((i, p))

        if g not in dic2:
            dic2[g] = p
        else:
            dic2[g] += p

    for (k, v) in sorted(dic2.items(), key=lambda x:x[1], reverse=True):
        for (i, p) in sorted(dic1[k], key=lambda x:x[1], reverse=True)[:2]:
            answer.append(i)

    return answer

가장 추천수 높은 풀이

def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
    genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
    return answer