프로그래머스 문제 풀이 베스트 앨범

문제 URL 베스트 앨범

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번 문제는 주어진 입력 음악의 genres, 음악의 플레이 횟수 plays를 이용하여 다음을 조건을 만족하는 리스트를 만드는 것입니다.

 

1. 총 플레이 횟수가 많은 genre 별로 내림차순으로 정렬되어야 한다.
2. 장르 내에서도 play 횟수 내림차순, 고유 번호 오름차순으로 정렬되어야 한다.
3. 한 장르 당 최대 2개까지만 뽑아서, 플레이 목록을 만들 수 있다.
4. 플레이 목록은 고유 번호로 하는 리스트이다.

이것들을 만족하는 리스트를 어떻게 만들 수 있을까요? 먼저 고유 번호는 각 배열의 인덱스를 뜻합니다. 입력에 대해서 표로 표현하면 다음과 같습니다.

 

인덱스	0	1	2	3	4
장르	classic	pop	classic	classic	pop
플레이 횟수	500	600	150	800	2500

 

자 이제 먼저 총 플레이 횟수가 많은 장르별로 정렬해봅시다. 먼저 { 장르 : 총 재생 횟수 } 형태로 저장하는 해시를 만들어줍니다.

 

{ classic : 1450, pop : 3100 }

 

이 해시를 토대로 총 재생 횟수 역순으로 장르를 정렬합니다.

[ ("pop", 3100), ("classic", 1450) ]

 

이제 장르별로 플레이 목록들을 정렬하기 위해서 { 장르 : [ (재생횟수, 고유 번호) ] } 형태로 저장하는 해시를 만들어줍니다.

{ "classic" : [ { 500, 0 }, { 150, 2 }, { 800, 3 }, ], "pop" : [ { 600, 1 }, { 2500, 4 }, ] }

 

이제 여기서 각각 재생 횟수 내림차순, 고유 번호 오름차순 즉 1차 기준을 재생 횟수 만약 같을 시에는 고유 번호로 정렬합니다. 그럼 해시는 다음과 같아집니다.

 

{ "classic" : [ { 800, 3 }, { 500, 0 }, { 150, 2 }, ], "pop" : [ { 2500, 4 }, { 600, 1 }, ] }

 

여기서 아까 만들어두었던 "총 재생 횟수의 내림차순으로 정렬한 장르 정보를 순회하여, 최대 2개까지 고유번호를 뽑아서 리스트를 만듭니다.

 

[ 4, 1, 3, 0 ]

 

어떻게 동작하는지 아시겠나요? 여기서 중요한 것은 "어떻게 목록을 정렬할 것인가"입니다. 이는 각 언어가 제공하는 정렬 알고리즘을 통해 손쉽게 구할 수 있습니다.

구르미의 알고리즘 풀이

이전 절에서 파악한 알고리즘을 정리하여 순서대로 나열하면 다음과 같습니다.

 

1. { 장르 : 총 재생 횟수 } 해시, { 장르 : [ { 플레이 횟수 : 고유 번호 } ] } 해시를 만듭니다.
2. 음악 개수만큼 장르와, 플레이 횟수가 들어있는 배열들을 순회하여, 2개의 해시를 초기화합니다.
3. { 장르 : 총 재생 횟수 } 해시를 기초로 총 재생 횟수 내림 차순으로 장르들을 정렬합니다.
4. 3번에 의해 정렬된 장르에 대해서 다음을 순회합니다.
   1. 장르 내에서도 플레이 횟수 내림차순, 고유 번호 오름차순 별로 정렬합니다.
   2. 장르 내에서 최대 2개까지 뽑습니다.

 

파이썬 코드로 나타내면 다음과 같습니다.

 

def solution(genres, plays):
    answer = []
    # { 장르 : 총 재생 횟수 } 사전
    playsDict = {}
    # { 장르 : [ ( 플레이 횟수, 고유 번호 ) ] }
    d = { }

    # 사전들 초기화
    for i in range(len(genres)):
        genre = genres[i]
        play = plays[i]
        playsDict[genre] = playsDict.get(genre, 0) + play
        d[genre] = d.get(genre, []) + [ (play, i) ]
        
    # 재생 횟수 내림차순으로 장르별로 정렬
    genreSort = sorted(playsDict.items(), key=lambda x: x[1], reverse=True)
    
    # 재생 횟수 내림차순, 인덱스 오름차순 정렬
    # 장르별로 최대 2개 선택
    for (genre, totalPlay) in genreSort:
        d[genre] = sorted(d[genre], key=lambda x: (-x[0], x[1]))
        answer += [ idx for (play, idx) in d[genre][:2] ]
    
    return answer


# test를 위한 메인 함수입니다.
if __name__ == '__main__':
   genres = ["classic", "pop", "classic", "classic", "pop"]	
   plays = [500, 600, 150, 800, 2500]
   result = solution(genres, plays)
   print(result)

 

파이썬의 sorted 함수는 강력합니다. "key"라는 메소드 파라미터에 람다 함수를 넘겨주었는데, 다음처럼 2개의 키를 준것을 확인할 수 있습니다.

 

# ... for (genre, totalPlay) in genreSort: d[genre] = sorted(d[genre], key=lambda x: (-x[0], x[1])) # ...

# ... 
for (genre, totalPlay) in genreSort: 
    d[genre] = sorted(d[genre], key=lambda x: (-x[0], x[1])) 
    # ...

 

 

여기서는 (플레이 횟수, 고유 번호) 형태로 리스트를 저장하기에, 이 2개를 키로 넘겨줄 수 있는 것입니다. 참고적으로 -를 붙이면 내림차순, +를 붙이면 오름차순으로 정렬됩니다. 물론 이 때 키는 숫자형 데이터타입이어야 합니다.

 

또한 위 코드는 파이써닉하게 표현하면, 위의 코드를 많이 줄일 수 있습니다. 그러나 그런 코드는 파이썬 한정에서만 쓸 수 있습니다. 저는 파이썬 외에도 여러 언어에 대해서도 적용하기 쉬운 알고리즘 코드를 만들기 위해서 위와 같이 표현했습니다. 다음은 같은 알고리즘의 CPP 코드입니다.

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

#include <iostream>

using namespace std;

vector<int> solution(vector<string>genres, vector<int> plays) {
    vector<int> answer;
    // { 장르 : 총 재생 횟수 } 사전
    map<string, int> playsMap;
    // { 장르 : [ ( 플레이 횟수, 고유 번호 ) ] }
    map<string, vector< pair<int, int>>> d;

    // 사전들 초기화
    for (int i=0; i<genres.size(); i++) {
        const auto & genre = genres[i];
        const auto & play = plays[i];
        playsMap[genre] = ( playsMap.find(genre) == playsMap.end() ) ? 0 : playsMap[genre];
        playsMap[genre] += play;
        d[genre] = ( d.find(genre) == d.end() ) ? vector< pair<int, int>>() : d[genre];
        d[genre].push_back( make_pair(play, i) );
    }

    // 재생 횟수 내림차순으로 장르별로 정렬
    vector< pair<string, int>> genreSort;
    
    for (const auto & elem : playsMap) {
        genreSort.push_back(elem);
    }
    
    sort(genreSort.begin(), genreSort.end(), [](pair<string, int> x, pair<string, int> y) {
        return x.second >= y.second;
    });

    // 재생 횟수 내림차순, 인덱스 오름차순 정렬
    // 장르별로 최대 2개 선택
    for (const auto & elem : genreSort) {
        string genre = elem.first;
        sort(d[genre].begin(), d[genre].end(), [](pair<int, int> x, pair<int, int>y){
            if (x.first == y.first) {
                return x.second < y.second;
            }

            return x.first >= y.first;
        });

        int idx = 0;

        for (const auto & p : d[genre]) {
            if (idx >= 2) {
                break;
            }

            answer.push_back(p.second);
            idx += 1;
        }
    }
    
    return answer;
}

// test를 위한 main 함수입니다.
int main() {
    vector<string> genres = { "classic", "pop", "classic", "classic", "pop" };
    vector<int> plays = { 500, 600, 150, 800, 2500 };
    auto result = solution(genres, plays);

    for (const auto & e : result) {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}