[프로그래머스] 베스트앨범 [C++] [lv.3]

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

프로그래머스

 

#문제 간단 정리

해시를 조금 더 복잡하게 사용하는 문제

#문제 해결 방법

일단 문제 설명이 복잡해서 조금 헷갈릴 수 있는데, 정리하자면

가장 높은 조회수를 기록한 장르의  조회수가 가장 높은 1,2번 곡들을 차례대로 

수록하는것이다

 

이걸 구현하기 위해서 우선

map 으로 장르별로 조회수를 취합하고

이걸 vector 로 복사해 정렬해서 장르별 순위를 알아낸다.

 

이 장르별 순위대로 

주어진 곡들 벡터를 순회하는데 현재 장르랑 같은 경우에

1순위 2순위를 갱신하도록한다,

그리고 순서대로 정답 벡터에 넣어주면된다

 

이해가 잘 안된다면 코드 주석을 살펴보자

 

#전체 코드

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

using namespace std;

bool valueComp(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second > b.second; // 장르별 총 재생 수에 따라 내림차순 정렬
}

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

    // 장르별 총 재생 수를 계산
    for (int i = 0; i < genres.size(); i++) {
        genreMap[genres[i]] += plays[i];
    }

    // 장르별 총 재생 수를 벡터로 이동
    vector<pair<string, int>> vec(genreMap.begin(), genreMap.end());

    // 벡터를 재생 수에 따라 정렬
    sort(vec.begin(), vec.end(), valueComp);

    vector<int> answer;
    for (int i = 0; i < vec.size(); i++) {
        pair<int, int> first = {-1, -1}; // 최대 재생수, 인덱스
        pair<int, int> second = {-1, -1}; // 두번째로 많은 재생수, 인덱스

        for (int j = 0; j < genres.size(); j++) {
            if (genres[j] == vec[i].first) {
                if (plays[j] > first.first) {
                    second = first; // 기존 첫번째 최대값을 두번째로 밀어냄
                    first = {plays[j], j}; // 새로운 최대값 설정
                } else if (plays[j] > second.first) {
                    second = {plays[j], j}; // 두번째 최대값 갱신
                }
            }
        }
        if (first.second != -1) answer.push_back(first.second);
        if (second.second != -1) answer.push_back(second.second);
    }
    
    return answer;
}