[프로그래머스]베스트앨범 C++문제풀이(map활용)

[프로그래머스]베스트앨범 C++문제풀이(map활용)

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

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

bool cmp(const pair<string, pair<int,pair<vector<int>,vector<int>>>> &a, const pair<string, pair<int,pair<vector<int>,vector<int>>>> &b)
{
    return a.second.first > b.second.first;
}

vector<int> solution(vector<string> genres, vector<int> plays)
{
    vector<int> answer;
    
    // <장르이름, <총플레이수, <음원인덱스,재생수> > >
    unordered_map<string, pair<int,pair<vector<int>,vector<int>>>>m_map;
    //unordered_map<string, tuple<int,int,vector<int>>>m_map;
    
    for(int i=0; i<genres.size(); i++)
    {
        m_map[genres[i]].first += plays[i];
        m_map[genres[i]].second.first.push_back(i);
        m_map[genres[i]].second.second.push_back(plays[i]);
    }
    
    // <장르이름, <총플레이수, <음원인덱스,재생수> > >
    vector<pair<string,pair<int,pair<vector<int>,vector<int>>>>>v(m_map.begin(),m_map.end());
    
    //총 재생횟수를 기준으로 내림차순 정렬
    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<v.size(); i++)
    {
        pair<vector<int>,vector<int>>temp = v[i].second.second;
        int size = temp.first.size()>=2 ? 2 :  temp.first.size();
        
        for(int j=0; j<size; j++)
        {
            int removeidx=0;
            int idx=-1;
            int maxvalue=0;
            for(int c=0; c<temp.second.size(); c++)
            {
                if(maxvalue < temp.second[c])
                {
                    maxvalue = temp.second[c];
                    idx = temp.first[c];
                    removeidx=c;
                }
            }
            answer.push_back(idx);
            
            temp.first.erase(temp.first.begin() + removeidx);
            temp.second.erase(temp.second.begin() + removeidx);
        }
    }
    
    return answer;
}

 

풀었던 문제중에 복잡한 편에 속한다.

문제를 봤을땐 쉬울줄 알았는데 생각보다 데이터 구조가 고려해야할 점이 많았음

괜히 레벨3가 아니였던듯 하다.

 

나는 맵을 하나로 처리했는데 그 때문에 맵의 키 밸류 구조가 좀 많이 복잡하다.

내가 만든 맵 구조는 이렇다 <장르이름, <총플레이수, <음원인덱스,재생수> > >

장르를 키 값으로 잡고 처리에 필요한 모든 데이터를 한방에 집어 넣었다.

해당 장르로 접근하면 그 장르에 총 플레이된 수, 그리고 음원의 인덱스와 그 음원의 재생수를 pair<vector<int>,vector<int>>로 저장하였다.

입력된 데이터를 해당 맵에 한꺼번에 넣은 후  '총 플레이 수' 로 내림차순 정렬하였다.

 

그 후 장르 개수만큼 반복분을 수행하여 가장 많이 재생된 노래 2개를 추출하여 노래의 인덱스를 vector에 넣고 반환한다.

이 부분에서 한가지 고려할 것은 해당 장르에 음원이 2개이상 없는 경우이다.

처음엔 for문을 2번 순회하라고 하드코딩 해놓았는데 에러가 났다.

pair<vector<int>,vector<int>>temp = v[i].second.second;
int size = temp.first.size()>=2 ? 2 :  temp.first.size();

다음처럼 해당 장르에 음원 개수가 2개 미만일 때는 아웃오브레인지가 나지않도록 처리해줬다.