Programmers - 여행경로

---

title: Programmers - 여행경로
date: 2022-07-29
tags:

• Algorithm

---

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

문제 요약

장르와 곡 재생 횟수, 고유 번호가 주어진다.
가장 많이 플레이 된 장르 순서 - 장르 내에서 많이 재생된 순서 - 재생 횟수가 같다면 고유 번호가 낮은 순서로 최대 2곡까지만 넣어 return한다.

문제 풀이

각 장르별 재생 횟수를 정산한 후, 해당 장르별 곡에 대한 처리해야 한다.
unordered_map을 이용한다면 string 처리에 구애받지 않고 vector에 대한 처리만으로 해결할 수 있을 것이라 판단하였다.


장르 이름을 key로, 전체 재생 횟수와 각 장르별 수록곡을 element로 가지는 vector를 value로 사용하였다.
우선 전체 재생 횟수로 unordered_map을 정렬한다. 이 때 처리의 용이를 위하여 vector에 넣어 처리하였다.
각 장르마다 곡에 대한 처리를 해준다. 장르 정렬이 끝났으므로 장르에 대한 것은 이제 잊어도 된다.
각 곡마다 재생 횟수와 고유 번호가 다르다. 이를 미리 정렬을 하면 앞에서부터 최대 2개의 곡만 확인하면 된다.
우선 첫 곡은 무조건 집어넣어야 한다. 해당 장르가 발견되었기에 수록곡이 한 개는 무조건 존재한다.
곡이 하나라면 그 곡만 집어넣되, 두 개 이상이라면 두 개까지 곡을 넣어야 한다. 물론 정렬하였기에 바로 뒤의 곡을 집어넣으면 된다.


Container가 너무 많이 중첩되어 unordered_map 처리가 매우 까다로웠다.
글에 기술하지는 않았으나 많은 삽질을 시도하다가, 결국 vector에 넣어 처리하는 것이 제일 무난하다고 판단하였다.

프로그램

#include <string>
#include <vector>
#include <unordered_map>
#include <utility>
#include <algorithm>

using std :: vector ;
using std :: string ;
using std :: unordered_map ;
using std :: pair ;
using std :: sort ;

struct songNode
{
    int iIndex ;
    int iPlayed ;

    songNode ( int iIndex , int iPlayed ) : iIndex ( iIndex ) , iPlayed ( iPlayed ) {}
} ;

bool comp ( pair < string , pair < int , vector < songNode > > > & a , pair < string , pair < int , vector < songNode > > > & 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 , vector < songNode > > > umGenrePlayed ;
    int iSongSize = genres.size () ;



    for ( int i = 0 ; i < iSongSize ; ++i )                        // Add song played group by genre
    {
        umGenrePlayed [ genres [ i ] ].first += plays [ i ] ;
        umGenrePlayed [ genres [ i ] ].second.emplace_back ( i , plays [ i ] ) ;
    }

    vector < pair < string , pair < int , vector < songNode > > > > vUmToVector ( umGenrePlayed.begin () , umGenrePlayed.end () ) ;            // Convert to vector to process easily
    std :: sort ( vUmToVector.begin () , vUmToVector.end () , comp ) ;
    iSongSize = vUmToVector.size () ;

    for ( int i = 0 ; i < iSongSize ; ++i )
    {
        vector < songNode > vSongList = vUmToVector [ i ].second.second ;
        sort ( vSongList.begin () , vSongList.end () , [] ( songNode & a , songNode & b )            // Sort by played, and index
              {
                  if ( a.iPlayed > b.iPlayed )
                      return true ;
                  else if ( ( a.iPlayed == b.iPlayed ) && ( a.iIndex < b.iIndex ) )
                      return true ;
                  return false ;
              } ) ;

        answer.emplace_back ( vSongList [ 0 ].iIndex ) ;

        if ( 1 != vSongList.size () )
        {
            answer.emplace_back ( vSongList [ 1 ].iIndex ) ;
        }
    }


    return answer ;
}