[Algorithm] 프로그래머스 베스트앨범 c++ (Map 활용)

알고리즘 풀이는 python으로 구현한 글에 있다.

여기서는 C++의 Map을 활용하는 방법을 기록하기 위해 같은 알고리즘을 들고왔다.

 

Map 활용 예시

선언

#include <map>

map<string, int> genresCnt; //key=string, value=int
map<int, int> playsCnt; //key=int, value=int

 

삽입

//1. insert와 make_pair 활용
genresCnt.insert(make_pair(genre, plays[i]));

//2. 배열처럼 사용
genresCnt[genre] += plays[i];

 

조회

genresCnt.count(genre) //genre는 key -> key에 해당하는 value 개수 반환

 

정렬

map자체를 정렬하는 것이 아니라 map을 vector로 변환 후, vector를 정렬해야 한다.

vector<pair<string, int>> v;
for(auto it=genresCnt.begin(); it!=genresCnt.end(); it++)
    v.push_back(make_pair(it->first, it->second));
sort(v.begin(), v.end(), cmp);

//내림차순 정렬
int cmp(pair<string, int>& v1, pair<string, int>& v2){
	return v1.second > v2.second;
}

 

초기화

playsCnt.clear();

 

 

소스코드

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

vector<string> genres;
vector<int> plays;

map<string, int> genresCnt;
map<int, int> playsCnt;

int cmp(pair<string, int>& v1, pair<string, int>& v2){
	return v1.second > v2.second;
}

int cmp2(pair<int, int>& v1, pair<int, int>& v2){
	return v1.second > v2.second;
}

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

    //1. key-value 구조화
    for(unsigned int i=0; i<genres.size(); i++){
    	string genre = genres[i];
    	if(genresCnt.count(genre))
    		genresCnt[genre] += plays[i];
    	else
    		genresCnt.insert(make_pair(genre, plays[i]));
    }

    //2. map -> vector 치환 후 value 기준으로 내림차순 정렬
    vector<pair<string, int>> v;
    for(auto it=genresCnt.begin(); it!=genresCnt.end(); it++)
    	v.push_back(make_pair(it->first, it->second));
    sort(v.begin(), v.end(), cmp);


    //3. v(정렬된 genresCnt) 탐색
    for(unsigned int i=0; i<v.size(); i++){
    	//3-1. 각 index(v의 key)에 해당하는 plays -> key-value로 구조화
    	for(unsigned int j=0; j<genres.size(); j++){
    		if(v[i].first == genres[j])
    			playsCnt[j] = plays[j];
    	}

    	//3-2. map -> vector 치환 후 value 기준으로 내림차순 정렬 
    	vector<pair<int, int>> v2;
        for(auto it=playsCnt.begin(); it!=playsCnt.end(); it++)
        	v2.push_back(make_pair(it->first, it->second));
        sort(v2.begin(), v2.end(), cmp2);

        //3-3. 앞에서부터 2개의 key를 answer에 추가
        int cnt = 0;
        for(unsigned int j=0; j<v2.size(); j++){
        	if(cnt > 1) break;
        	answer.push_back(v2[j].first);
        	cnt++;
        }
        playsCnt.clear();
    }

    return answer;
}