알고리즘(C++) / 프로그래머스 level 3 : 베스트앨범

level 3 : 베스트앨범

https://programmers.co.kr/learn/courses/30/lessons/42579?language=cpp 

코딩테스트 연습 - 베스트앨범

 

코드

//프로그래머스 베스트앨범
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>

using namespace std;

bool cmp(pair<string, int> & a, pair<string, int>& b) {
    return a.second > b.second;
} //내림차순

bool cmp_play(pair<int, int>& a, pair<int, int>& b) {
    if (a.first == b.first) {
        return a.second < b.second; //오름차순
    }
    return a.first > b.first; //내림차순
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;

    unordered_map<string,int> m;
    for (int i = 0; i < genres.size(); i++) {
        m[genres[i]] += plays[i];
    }//해쉬맵

    vector<pair<string, int>> v(m.begin(), m.end()); //vector로 copy
    sort(v.begin(), v.end(), cmp); //정렬

    for (int i = 0; i < v.size(); i++) {
        vector<pair<int, int>> genre;
        for (int j = 0; j < plays.size(); j++) {
            if (v[i].first == genres[j]) {
                genre.push_back(make_pair(plays[j], j));
            }
        }
        sort(genre.begin(), genre.end(), cmp_play); //정렬

        //장르에 속한 곡이 하나라면, 하나의 곡만 선택
        answer.push_back(genre[0].second);
        if (genre.size() >= 2) {
            answer.push_back(genre[1].second);
        }
    }
    
    return answer;
}

int main() {
    vector<string> genres = { "classic", "pop", "classic", "classic", "classic",  "classic" };
    vector<int> plays = { 500, 1000, 400, 300, 200, 100 };
    solution(genres, plays);


    return 0;
}

 

설명

• 이번 문제는 해시맵을 사용하는 것이다.
• 이번 문제에서 unordered_map을 사용하였다. 문자열을 키로 사용하고 장르의 합을 구할 수 있었다. 장르의 플레이 합을 내림차순으로 정렬한다.
• 정렬된 순서대로 장르를 찾아 플레이 횟수와 고유 번호를 pair 쌍으로 genre 벡터에 저장한다.
• genre 벡터을 플레이 횟수 순으로 정렬하고 플레이 횟수가 같다면 고유번호의 오름차순으로 정렬한다.
• 정렬한 genre 벡터에서 플레이 횟수가 가장 많은 노래 두개를 answer 벡터에 저장한다. 

 

고찰

문제를 제대로 안읽고 풀어서 제대로 조건을 파악되지 않았다.... 그래서 계속 틀렸었다.......

5~14번까지 틀렸었다. 그 이유는 장르 별로 가장 많이 재생된 노래를 두개씩 모으는 것인데 가장 많이 재생된 장르 중 2개의 장르만 선택하는 줄 알았다. 하지만 모든 장르의 가장 많이 재생된 노래 두개 씩 모으는 것이었다.

문제를 다시 꼼꼼히 읽고 조건을 완벽하게 파악해야 할거 같다.