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

프로그래머스 베스트앨범 풀이입니다.

이 문제는 나와있는 조건을 잘 확인했어야 했다. (제대로 확인 못해서 뻘짓을 많이 하였다.) 전형적인 해시 문제이다!

조건은 다음과 같다.

• 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
• 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
• 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

들어오는 장르와 길이들을 우선 같은 장르끼리 묶어서 속한 노래가 많은 장르부터 찾는다.

찾은 뒤 그 장르 내에서 많이 재생된 노래 순으롱 정렬을 시키고 인덱스도 정렬하여 저장시킨다.

솔직히 좀 비효율적으로 코드를 짰다고 생각한다. 조만간 좀 효율적으로 수정해볼까 생각중이다.

Problem : 베스트앨범

Source Code(C++) :

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

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

	map<string, int> mp;
	map<string, int>::iterator iter;

	for (int i = 0; i < genres.size(); i++) {
		iter = mp.find(genres[i]);
		if (iter != mp.end()) {
			mp[genres[i]] = iter->second + plays[i];
		}
		else {
			mp.insert({genres[i],plays[i]});
		}
	}

	map<int, string> rev; // 번호순으로 재배치
	map<int, string>::iterator it;

	for (iter = mp.begin(); iter != mp.end(); iter++) {
		rev.insert({-(iter->second),iter->first});
	}

	vector<pair<int, int>> arr;

	for (it = rev.begin(); it != rev.end(); it++) {
		string tmp = it->second;
        arr.clear();
		for (int i = 0; i < genres.size(); i++) {
			if (tmp == genres[i])
				arr.push_back({ -plays[i], i });
		}

		sort(arr.begin(), arr.end());

		if (arr.size() == 1)
			answer.push_back(arr[0].second);
		else {
			answer.push_back(arr[0].second);
			answer.push_back(arr[1].second);
		}	
	}
	return answer;
}

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이