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

문제

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

풀이

따로 생각할 필요없이 문제가 시키는대로 구현하면 되는데 자료구조를 잘 이용해야 한다.
⭐이런 유형 코테에서 엄청 많이 나왔었던 것 같다.⭐

1. 문제에서 사용한 자료구조
   이중 map
   music : (클래식, 1450), (팝, 3100)
   
   musiclist :
   클래식 (3, 800), (0, 500), (2, 150)
   팝 (4, 2500), (1, 1600)

map<string, int> music;
map<string, map<int, int>> musiclist;

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

	// m[1] = 100;
    // map에 요소 삽입

	music[genres[i]] += plays[i];
    musiclist[genres[i]][i] = plays[i];
}

2. 풀이

• 제일 많이 재생된 장르 찾고
• 장르 내에서 제일 많이 재생된 곡 찾아서 (2번 반복)
• answer에 index 넣고, music이랑 musiclist에서 erase 해주기 (장르 전부 erase 될 때까지 반복)

로직은 단순한데 이중 map이랑 범위 기반 for문을 적절히 사용해서 코드를 작성해야 한다.

코드

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

using namespace std;

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> music;
    map<string, map<int, int>> musiclist;
    
    for(int i=0; i<genres.size(); i++) {
        music[genres[i]] += plays[i];
        musiclist[genres[i]][i] = plays[i];
    }
    
    while(music.size() > 0) {
        string genre = "";
        int max = 0;
        
        for(auto m : music) { //제일 많이 재생된 장르 찾기
            if(max < m.second) {
                max = m.second;
                genre = m.first;
            }
        }
        
        for(int i=0; i<2; i++) {
            int val = 0;
            int index = -1;
            for(auto ml : musiclist[genre]) { //장르 내에서 제일 많이 재생된 곡 찾기
                if(val < ml.second) {
                    val = ml.second;
                    index = ml.first;
                }
            }
            
            if(index == -1) break; //두곡 미만일 경우
            
            answer.push_back(index);
            musiclist[genre].erase(index);
        }
        
        music.erase(genre);
    }
    
    return answer;
}