[프로그래머스/파이썬] 베스트앨범

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

프로그래머스

문제 요약 : 장르를 나타내는 genres, 노래별 재생횟수를 나타내는 plays가 주어질 때 베스트 앨범에 들어갈 노래의 고유번호를 순서대로 return하라. 베스트 앨범에 들어가는 노래는 장르당 두개씩이고, 가장 재생횟수가 많은 장르순, 가장 재생횟수가 많은 노래순, 고유번호가 낮은순으로 배열된다.

 

 

 

이번 문제를 풀면서 알아야하는 개념은 크게 세가지라고 생각된다. 먼저 해시 알고리즘, 그리고 그를 구현하기 위한 파이썬의 딕셔너리 데이터 타입, 그리고 마지막으로 딕셔너리 내 정렬을 도와주는 lambda이다.

 

1. 해시 알고리즘(Hash Algorithm)

해시란 임의의 크기를 가진 데이터(key)를 고정된 데이터(Value)로 변환시키는 것을 의미한다.

이를 통해 입력한 데이터의 값을 이용해 특정한 배열의 인덱스나 위치를 찾을 수 있다.

기존에 사용했던 자료구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비하여

해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있어 빠른 속도로 처리할 수 있다.(평균 시간복잡도O(1))

 

자세한 내용은 다른 포스팅으로 정리하도록 하겠음😉

 

2. 딕셔너리

딕셔너리는 위와 같은 해시테이블 자료 구조를 기반으로 하여 key값과 value값으로 이루어진 여러쌍의 데이터를 담아 둘 때 사용한다.

리스트처럼 가변(mutability) 데이터 타입이기 때문에 자유롭게 새로운 키에 값을 추가하거나 기존 키의 값을 삭제할 수 있다.

데이터를 추가할 때에는 [<키>] = <값> 형태로 할당해줄 수 있으며, 값에 접근할 때에는 [<키>] 를 사용한다.

또한 in 연산자를 이용하여 사전에 있는 모든 데이터를 for루프문으로 순회할 수 있다. 기본적으로는 키만 얻어지기 때문에 값을 구하고자 하면 대괄호를 이용하여야한다.

 

3. lambda를 이용한 정렬

lambda는 매개변수를 입력하고 콜론을 넣은 다음 그를 이용한 식을 적어주게 되면 작동하는 가벼운 함수같은 개념이다.

예를 들어

def is_even(x):

    return x % 2 == 0 이라는 함수를

is_even = lamda x : x%2 == 0

으로 표현할 수 있다.

 

이러한 람다를 sorted함수에서 이용할 수있는데,

리스트 a가 주어졌을때 a의 첫번째 값을 기준으로

sorted(a, key=lambda x : x[0]) : 오름차순 정렬

sorted(a, key=lambda x : -x[0]) : 내림차순 정렬

을 할 수 있다.

 

추가로, 파이썬에는 정렬을 하는 함수가 두가지가 존재하는데 바로 sort()와 sorted()이다.

sort() : 리스트명.sort() 형식으로 "리스트형의 메소드"이며 리스트 원본의 값을 직접 수정한다.

sorted() : sorted(리스트명) 형식으로 "내장 함수"이며 원본값은 그대로이고 정렬값을 반환한다.

 

 

 

풀이 )

해시문제는 거의 풀어보지 못해서 많이 배우면서 풀었던 문제이다.

먼저 total에 장르가 같고 (x[0]), 재생횟수가 크고 (-x[1]), 고유번호가 낮은순으로(x[2]) sorted해준다.

 

그 다음 장르별 재생횟수를 계산하기 위하여 딕셔너리를 이용한다. 이때, in연산자를 이용하여 키값을 비교해주면 쉽게 구현할 수 있다.

 

다음 저장된 장르를 key내림차순으로(장르별 재생횟수가 큰 순)정렬해준다.

 

이렇게 정렬된 장르와 저장된total을 비교하며 ans에 고유번호를 두개씩 넣어주고, return해준다.

def solution(genres, plays):
    ans = []
    n = len(genres)
    Genre = {}
    
    # 장르같은 순, 재생횟수 큰 순, 고유번호 낮은 순으로 저장
    total = [[genres[i],plays[i],i] for i in range(n)]
    total = sorted(total, key=lambda x : (x[0], -x[1], x[2]))
    
    # 장르별 재생횟수 dic에 저장
    for i in total :
        if i[0] not in Genre:   #i[0]이 Genre key값에 존재하는지
            Genre[i[0]] = i[1]
        else :
            Genre[i[0]] += i[1]
    
    # Genre dict을 key 내림차순으로 정렬, [()] 형태로 변환
    Genre = sorted(Genre.items(), key=lambda x : -x[1])
    
    # ans에 각 장르 두개 씩 추가
    for i in range(len(Genre)):
        tmp = 0
        for j in range(n):
            if (Genre[i][0] == total[j][0]) and (tmp < 2) :
                ans.append(total[j][2])
                tmp += 1

    return ans