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

https://programmers.co.kr/learn/courses/30/lessons/42579?language=cpp 

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

 

시도하다가 복잡해니까 포기했다,,

#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 mu : music){ // 장르 중 제일 높은 것 찾기
            if(max < mu.second){
                max = mu.second;
                genre = mu.first;
            }
        }
        for(int i=0; i<2; i++){
            int val = 0, ind = -1;
            for(auto ml : musiclist[genre]){ // 노래 중 제일 높은 것
                if(val < ml.second){
                    val = ml.second;
                    ind = ml.first;
                }
            }
            if(ind == -1) break; // 만약 노래가 1곡 이하면 탈출
            
            answer.push_back(ind); // 리턴할 리스트에 노래번호 추가
            musiclist[genre].erase(ind);
        }
        music.erase(genre); // map에서 사용한 장르삭제
        
    }
    
    return answer;
}

 

다른 풀이 참고,,

하나씩 분석해보자

map<string, int> music; //각 장르별 횟수 저장
map<string, map<int, int>> musiclist; //각 장르별 무슨 노래별 횟수

우선 map 두개를 선언한다

 

for(int i=0;i<genres.size();i++){
    music[genres[i]] += plays[i];
    musiclist[genres[i]][i] = plays[i];
}

노래의 수 만큼 반복

map<string, int> music 에는 장르별 재생횟수가 저장되고,

map<string, map<int, int>> musiclist 에는 장르별/ 노래별 재생횟수가 저장 됨

 

<music>

classic	1450
pop	3100

 

<musiclist>

	0	1	2	3	4
classic	500		150	800
pop		600			2500

 

string genre{};
int max{0};​

for 문 안에 변수 선언

 

for(auto mu : music){ // 장르 중 제일 높은 것 찾기
     if(max < mu.second){
         max = mu.second;
          genre = mu.first;
      }
}

max = 3100

genre = pop 이 됨

 

2곡씩이라 2번 반복

int val = 0, ind = -1;
for(auto ml : musiclist[genre]){ // 노래 중 제일 높은 것
     if(val < ml.second){
          val = ml.second;
          ind = ml.first;
      }
}
if(ind == -1) break; // 만약 노래가 1곡 이하면 탈출
            
answer.push_back(ind); // 리턴할 리스트에 노래번호 추가
musiclist[genre].erase(ind);

genre = pop 이어서

val = 2500, ind = 4 가 됨

 

answer 에 4를 넣음

 

musiclist[pop] 에서 4를 지움

 

<musiclist>

	0	1	2	3	4
classic	500		150	800
pop		600			2500

 

int val = 0, ind = -1;
for(auto ml : musiclist[genre]){ // 노래 중 제일 높은 것
    if(val < ml.second){
        val = ml.second;
        ind = ml.first;
    }
}
if(ind == -1) break; // 만약 노래가 1곡 이하면 탈출
            
answer.push_back(ind); // 리턴할 리스트에 노래번호 추가
musiclist[genre].erase(ind);

genre = pop 이고

val = 600, ind = 1 이 되고

answer 에 1이 들어감

 

musiclist[pop] 에서 1을 지움

 

<musiclist>

	0	1	2	3	4
classic	500		150	800
pop		600			2500

2번 반복 완료

 

music.erase(genre); // map에서 사용한 장르삭제

music 에서 pop 삭제

 

<music>

classic	1450
pop	3100

 

string genre{};
int max{0};
        
for(auto mu : music){ // 장르 중 제일 높은 것 찾기
    if(max < mu.second){
         max = mu.second;
         genre = mu.first;
    }
}

max = 1450 , genre = classic 이 됨

 

2곡씩이라 2번 반복

int val = 0, ind = -1;
for(auto ml : musiclist[genre]){ // 노래 중 제일 높은 것
       if(val < ml.second){
            val = ml.second;
            ind = ml.first;
       }
}
if(ind == -1) break; // 만약 노래가 1곡 이하면 탈출
            
answer.push_back(ind); // 리턴할 리스트에 노래번호 추가
musiclist[genre].erase(ind);

첫번째 결과  musiclist[classic]에서 재생횟수가 가장 많은 노래를 찾는 것이기 때문에

val = 800, ind = 3이 됨

 

answer에 3이 들어가고

musiclist[classic]에서 3번이 지워짐

 

<musiclist>

	0	1	2	3	4
classic	500		150	800
pop		600			2500

 

두번째 결과  그 다음으로 많은

 val = 500, ind = 0 이 됨

 

answer에 0이 들어가고 

musilclist[classic]에서 0번이 지워짐

 

<musiclist>

	0	1	2	3	4
classic	500		150	800
pop		600			2500

 

2번 반복 완료

 

music.erase(genre); // map에서 사용한 장르삭제

music에서 classic 삭제

 

<music>

classic	1450
pop	3100

 

music.size()가 0이기 때문에 while문을 빠져나옴

 

return answer;

answer을 리턴하게 되면

 

push한 순서대로 4, 1, 3, 0 이 나오게 된다.

 

 

그리고 다른 풀이 : 함수를 쓰고 효율적으로 보인다

https://ongveloper.tistory.com/75

프로그래머스 베스트앨범 c++ (해시)