[프로그래머스 베스트앨범] c++ (풀이, 코드, map과vector 정복)

문제 링크

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

프로그래머스

문제

 

풀이, 코드

사실 이런 문제에 대해서 풀려고 진행을 할때 느끼는 점은 까먹었던 모든것들에 대해서 다시 다 일깨워주는 기분입니다.

 

뭐 map이 key가 없을때 value인 pair<int,int>이던 int던 {0,0} , 0으로 불리는 것들과 pair를 이것저것에서 사용을 해보고 

조금 더럽긴 하지만 first[v[i].first].second과 같이 혼종도 만들 수 있는 것 같습니다..ㅎㅎㅎ

 

잡설은 그만하고 제 풀이, 알고리즘에 대해서 설명드리도록 하겠습니다.

 

1. 선언부 -> 장르와 합에 대한 map/ 마지막 정렬을 하고 출력해줄 vector v

                    장르중 가장 큰값과 두번째값 맵 (pair로 plays[인덱스]와  인덱스를 value로 넣어줍니다.)

 

2. 알고리즘

     1) 항상 기초틀은 합을 해주는 map m 에 대해서는 계속 += plays[i]를 해줍니다.

     2) 처음 나오는 장르는 first에 푸쉬해줍니다

     3) 두번째일때 값이 크다면!! first가 second로가고 first에는 새로운 것을 넣어줍니다.

     4) 이제 세개이상의 값이 생길때는 똑같이 비교하여 넣어줍니다.

 

#### 주의!! -> 값이 같다면 인덱스 순서대로 하는것이기 때문에 비교연산자에 대해서 신경을 써줘야합니다.

 

 

3. 처리부분

   1) 벡터에 map에 대해서 넣어주고 역순으로 정렬을 해줍니다.

   2) 정렬이 된 벡터의 string을 first와 second의 맵에 확인을 해줍니다

        (여기서 또 first만 들어올 수 있으니 second를 할때는 확인을 해줘야합니다.)

        answer.push_back(first[v[i].first].second);
        if(second[v[i].first].first != 0){
            answer.push_back(second[v[i].first].second);
        }

 

#include <string>

#include <vector>

#include <algorithm>

#include <map>

using namespace std;

bool compare(pair<string,int>&a, pair<string,int>&b){

    return a.second > b.second;

}

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

    vector<int> answer;

    int len = genres.size();

   

    map<string,int> m; //장르이름, 합 저장

    vector<pair<string,int>> v;

    map<string,pair<int,int>> first; // plays[인덱스]와 인덱스

    map<string,pair<int,int>> second; // 동일

   

   

    for(int i = 0; i < len;i++){

        if(first[genres[i]].first == 0) // 처음일때

            first[genres[i]] = {plays[i],i};

        else if(second[genres[i]].first == 0){ //두번째일때

            if(plays[i] >first[genres[i]].first){

                second[genres[i]] = first[genres[i]];

                first[genres[i]] = {plays[i],i};

            }

            else{

                second[genres[i]] = {plays[i],i};

            }

        }else{

            if(plays[i] > first[genres[i]].first){

                second[genres[i]] = first[genres[i]];

                first[genres[i]] = {plays[i], i};

            }else if(second[genres[i]].first < plays[i] &&plays[i]<=first[genres[i]].first){

                second[genres[i]] = {plays[i],i};

            }

            //작은 경우 무시

        }

        m[genres[i]] += plays[i];

    }

   

    for(const auto& pair : m){

        v.push_back(pair);

    }

   

    sort(v.begin(),v.end(),compare);

   

    for(int i = 0; i < v.size();i++){

        answer.push_back(first[v[i].first].second);

        if(second[v[i].first].first != 0){

            answer.push_back(second[v[i].first].second);

        }

    }

   

    return answer;

}

 

전체에 대한 생각과 더불어 까먹었던 부분에 대해서 다시 상기가 되고 디테일적인 부분(비교 연산)에 대해서도 조금은 신경을 써줘야 하는 문제라 개인적으로 도움이 되는 문제라고 생각합니다.