(프로그래머스) 베스트앨범

문제 링크

• 프로그래머스

요약

• 시간투자해야되는 구현문제

최종 §

결과

• 다음의 순서대로 수행하도록 한다:
  1. 필요한 자료구조들을 채운다.
  2. 장르를 총 play 수에 따라 정렬한다.
  3. 각 장르별 노래를 play 수에 따라 정렬한다.
  4. 각 장르별로 가장 많이 play 된 두 노래를 꺼내 결과 vector 에 넣는다.
• 코드를 보자.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
struct Genre {
	int id;
	int play_cnt;
};
 
struct Song {
	int id;
	int play_cnt;
};
 
vector<int> solution(vector<string> genres, vector<int> plays) {
	int I = genres.size();
	map<string, int> genre_id;
	vector<Genre> genre_cnt;
	vector<vector<Song>> songs;
	vector<int> ret;
 
	for (int i = 0; i < I; i++) {
		if (genre_id.find(genres[i]) == genre_id.end()) {
			genre_id[genres[i]] = genre_id.size();
			genre_cnt.push_back({genre_id[genres[i]], 0});
			songs.push_back(vector<Song>());
		}
 
		genre_cnt[genre_id[genres[i]]].play_cnt += plays[i];
		songs[genre_id[genres[i]]].push_back({i, plays[i]});
	}
 
	sort(genre_cnt.begin(), genre_cnt.end(), [](auto &a, auto &b) {
		return a.play_cnt > b.play_cnt;
	});
 
	for (auto &s : songs) {
		sort(s.begin(), s.end(), [](auto &a, auto &b) {
			if (a.play_cnt == b.play_cnt) {
				return a.id < b.id;
			} else {
				return a.play_cnt > b.play_cnt;
			}
		});
	}
 
	for (auto &g : genre_cnt) {
		auto &s = songs[g.id];
 
		for (int i = 0; i < 2 && i < s.size(); i++) {
			ret.push_back(s[i].id);
		}
	}
 
	return ret;
}

1. L25-L34: 필요한 자료구조들을 채운다.
   • genre_id: 장르이름(string) -> 장르 ID(int) 변환을 위한 map
   • genre_cnt: 각 장르에 대한 Genre 구조체를 담는 vector
   • songs: 각 장르에 속하는 노래들을 담는 vector. 즉, songs[장르 ID] 는 해당 장르에 속하는 노래들의 Song 구조체 vector 이다.
2. L36-L38: 장르를 총 play 수에 따라 정렬한다.
   • 이건 그냥 Genre::play_cnt 로 정렬하면 된다.
3. L40-L48: 각 장르별 노래를 play 수에 따라 정렬한다.
   • 이건 각 장르 vector 에 대해 Song::play_cnt 로 정렬하면 된다.
   • 문제조건에 나온 대로, Song::play_cnt 가 같다면 Song::id 로 정렬한다.
4. L50-L56: 각 장르별로 가장 많이 play 된 두 노래를 꺼내 결과 vector 에 넣는다.
   • genre_cnt 를 순회하면서, 해당 장르에 해당하는 songs 의 vector (즉, songs[g.id]) 에서 노래 두개를 꺼내면 된다.