C++ / 프로그래머스 / 베스트앨범

문제

 

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

프로그래머스

문제풀이

 

맵과 우선순위 큐를 이용해서 풀었다. 맵 안에 우선순위 큐가 들어가 복잡해 보일 수 있지만, 풀이는 간단하다.

 

map<string, int>를 선언해서 장르별로 총 재생된 횟수를 기록한다. (string = 장르, int = 재생된 횟수)

map<string, 우선순위큐>를 선언했는데, 우선순위 큐는 pair<int, int> 형태로 되어있다. {재생된 횟수, 곡 번호}

 

struct compare {
    bool operator()(pair<int, int>& song1, pair<int, int>& song2) {
        if (song1.first == song2.first) {
            return song1.second < song2.second;
        }
        return song1.first > song2.first;
    }
};

장르별 최대 2곡이므로 우선순위큐를 정렬할 때 top부분에 낮은 재생된 횟수, 높은 곡 번호순으로 해야 한다.

(우선순위 큐를 pop 하면서 곡을 교체할 것이므로 문제에 필요한 높은 재생된 횟수, 낮은 번호는 끝에 가있어야 한다.)

 

bool cmp(pair<string, int>& genre1, pair<string, int>& genre2) {
    return genre1.second > genre2.second;
}

또 맵을 key가 아닌 value로 정렬할 것이기 때문에 벡터를 따로 선언하여 복사하고 정렬했다.

(장르의 이름 순이 아닌 재생된 횟수로 정렬하기 위함)

 

    for (idx = 0; idx < plays.size(); ++idx) {
        genre[genres[idx]] += plays[idx];
        songs[genres[idx]].push({ plays[idx],idx });
        if (songs[genres[idx]].size() > 2) {
            songs[genres[idx]].pop();
        }
    }

genre는 map[장르] = 재생된 횟수를 나타내는 맵이다.

여기서 장르별로 재생된 횟수를 계속 더한다.

songs는 map<string, 우선순위큐>로 장르별 2곡을 저장하기 위함이다.

따라서 조건문으로 크기가 2를 넘을 시 pop을 하여 최대 2곡을 유지시킨다.

 

    vector<pair<string, int>>v(genre.begin(), genre.end());
    sort(v.begin(), v.end(), cmp);

map[장르] = 재생된 횟수는 재생된 횟수가 큰 순으로 정렬되어있지 않다. (value 이므로)

따라서 벡터를 선언하여 복사하고 정렬한다.

 

    for (idx = 0; idx < genre.size(); ++idx) {
        if (songs[v[idx].first].size() == 1) {
            answer.push_back(songs[v[idx].first].top().second);
            songs[v[idx].first].pop();
        }
        else {
            song2 = songs[v[idx].first].top().second;
            songs[v[idx].first].pop();
            song1 = songs[v[idx].first].top().second;
            songs[v[idx].first].pop();

            answer.push_back(song1);
            answer.push_back(song2);
        }
    }

v[idx]. first는 map <string, int>에서 string 부분이다. 위에서 재생 수 기준 내림차순으로 정렬을 했다.

songs[장르]의 크기가 1이라면 (우선순위큐), top부분을 바로 answer에 push_back()하면 된다.

 

songs[장르]의 크기가 2라면, 이전에 우선순위 큐는 top부분에 재생된 횟수가 작고, 곡 번호가 높은 것이 먼저 오도록 정렬했으므로 answer에 입력할 때 순서를 바꿔 입력해야 한다.

따라서 입력하기 전에 정보를 미리 저장하고 answer에 순서를 바꿔 입력한다.

 

코드

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

struct compare {
    bool operator()(pair<int, int>& song1, pair<int, int>& song2) {
        if (song1.first == song2.first) {
            return song1.second < song2.second;
        }
        return song1.first > song2.first;
    }
};

bool cmp(pair<string, int>& genre1, pair<string, int>& genre2) {
    return genre1.second > genre2.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    int idx(0), song1(0), song2(0);
    vector<int> answer;
    map<string, int>genre;
    map<string, priority_queue<pair<int, int>, vector<pair<int, int>>, compare>>songs;

    for (idx = 0; idx < plays.size(); ++idx) {
        genre[genres[idx]] += plays[idx];
        songs[genres[idx]].push({ plays[idx],idx });
        if (songs[genres[idx]].size() > 2) {
            songs[genres[idx]].pop();
        }
    }
    
    vector<pair<string, int>>v(genre.begin(), genre.end());
    sort(v.begin(), v.end(), cmp);
    
    for (idx = 0; idx < genre.size(); ++idx) {
        if (songs[v[idx].first].size() == 1) {
            answer.push_back(songs[v[idx].first].top().second);
            songs[v[idx].first].pop();
        }
        else {
            song2 = songs[v[idx].first].top().second;
            songs[v[idx].first].pop();
            song1 = songs[v[idx].first].top().second;
            songs[v[idx].first].pop();

            answer.push_back(song1);
            answer.push_back(song2);
        }
    }

    return answer;
}