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

문제 풀이

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

using namespace std;

// make_pair를 사용했기 때문에 인자도 pair로 받는다.
bool pg_cmp(pair<string, int> a, pair<string, int> b) {
	// int 부분을 비교. 여기서는 재생 횟수를 내림차순으로 비교하는 것이다. 큰것부터 가져오기 떄문.
	return a.second > b.second;
}

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

	// 각 장르의 총 재생횟수를 카운트
	map<string, int> genre_cnt;
	for (unsigned int i = 0; i < genres.size(); i++) 
		genre_cnt[genres[i]] += plays[i];
	
	// (장르, 총 재생횟수) 배열 생성
	vector<pair<string, int>> genre_totalcnt;
	for (auto it : genre_cnt)
		genre_totalcnt.push_back(make_pair(it.first, it.second));

	// 2차원 배열을 정렬하기 위해서는 cmp 함수를 커스텀해야 함. pg_cmp 부분을 확인.
	sort(genre_totalcnt.begin(), genre_totalcnt.end(), pg_cmp);

	// 장르 별로 가장 많이 재생된 두 곡 찾기
	for (unsigned int i = 0; i < genre_totalcnt.size(); i++) {
		// 첫 번째, 두 번째 곡의 재생횟수, 첫 번째, 두 번째 곡의 고유번호를 담기 위한 변수. 먼저 0으로 초기화시킨다.
		int first, second, first_id, second_id;
		first = second = first_id = second_id = 0;

		for (unsigned int j = 0; j < genres.size(); j++) {
			// 가장 많이 재생된 장르라면
			if (genres[j] == genre_totalcnt[i].first) {
				// first에 가장 큰 값을 넣기 위해 이전에 first 그룹에 있던 값들은 second 그룹으로 이전
				// 큰 값들은 first 그룹에 부여
				if (plays[j] > first) {
					second = first;
					second_id = first_id;
					first = plays[j];
					first_id = j;
				}
				// first보단 작고 second보다 크다면 그 값을 second 그룹에 부여
				else if (plays[j] > second) {
					second = plays[j];
					second_id = j;
				}
			}
		}
		// 한 곡 이상은 반드시 존재하니 첫 번째 곡의 고유번호를 먼저 넣고
		answer.push_back(first_id);
		// 두 번째 곡이 존재한다면 그 고유번호도 넣는다.
		if (second > 0)	answer.push_back(second_id);
	}
    
    return answer;
}

 

문제 링크

 

programmers.co.kr/learn/courses/30/lessons/42579

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