베스트앨범 [Lv. 3] (C++)

프로그래머스

N명의 사람이 있을 때 그 사람들이 들은 장르와, 플레이 타임을 입력받습니다.

이후 가장 많이 들은 장르의 순서 + 감상한 길이 순서로 사람들의 번호를 출력하면 됩니다.

 

EX)

Genre -> 클래식, 팝, 클래식, 클래식, 팝

plays -> 500, 600, 150, 800, 2500

return -> 팝의 플레이 타임이 가장 많고 4번이 가장오래 들었으니 4, 그다음 1번 출력

이후 클래식을 가장 많이 들은 두사람 번호 3, 0 출력 

 

풀이 방법

입력들을 순회하면서 장르의 플레이타임을 기록해줍니다.

가장 많이들은 두 사람을 기록해주고 총 플레이타임을 기준으로 정렬 후 사람의 index번호를 출력하면 되겠습니다.

플레이타임을 기록하는 부분은 map으로 장르를 탐색하고 기록하면 되겠습니다.

 

struct Genre
{
    Genre(string n)
    {
        name = n;
    }
        
    int total = 0;
    int first = 0;
    int second = 0;
    
    int first_idx = -1;
    int second_idx = -1;
    
    string name;
    
    void Add(int time, int idx)
    {
        total += time;
        if (first < time)
        {
            second = first;
            second_idx = first_idx;
            
            first = time;
            first_idx = idx;
        }
        else if (second < time)
        {
            second = time;
            second_idx = idx;
        }
    }
};

장르를 구조체로 만들었습니다.

장르에 플레이 타임과 index번호를 ADD함수로 넘기면 

total 값과 가장 많이 들은 사람의 index번호를 수정해줍니다.

이후 first_idx와 second_idx를 출력하면 됩니다.

 

struct map
{
    map(int size = 10000)
    {
        table.resize(size);
    }
    
    int hash(string str)
    {
        int key = 0;
        for (char& c : str)
            key += c - 'a';
        
        key %= table.size();
        return key;
    }
    
    void insert(string genre, int time, int idx)
    {
        int key = hash(genre);

        if (table[key].empty())
        {
            Genre g(genre);
            g.Add(time, idx);
            
            table[key].push_back(g);
        }
        else
        {
            for(auto& g : table[key])
            {
                if (g.name == genre)
                {
                    g.Add(time, idx);
                    return;
                }
            }
            
            Genre temp(genre);
            temp.Add(time, idx);
            table[key].push_back(temp);
        }
    }
    
    vector<vector<Genre>> table;
};

unorderded_map입니다. string을 key로 변경 후에 table에 저장하는 방식입니다.

key가 같을 경우 vector를 순회하여 찾습니다.

table의 사이즈를 크게 키우면 중복되는 key가 줄어듭니다.

insert함수에서 플레이타임과 index를 입력받아서 처리해줍니다.

 

전체 코드

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Genre
{
    Genre(string n)
    {
        name = n;
    }
        
    int total = 0;
    int first = 0;
    int second = 0;
    
    int first_idx = -1;
    int second_idx = -1;
    
    string name;
    
    void Add(int time, int idx)
    {
        total += time;
        if (first < time)
        {
            second = first;
            second_idx = first_idx;
            
            first = time;
            first_idx = idx;
        }
        else if (second < time)
        {
            second = time;
            second_idx = idx;
        }
    }
};

struct map
{
    map(int size = 10000)
    {
        table.resize(size);
    }
    
    int hash(string str)
    {
        int key = 0;
        for (char& c : str)
            key += c - 'a';
        
        key %= table.size();
        return key;
    }
    
    void insert(string genre, int time, int idx)
    {
        int key = hash(genre);
        if (table[key].empty())
        {
            Genre g(genre);
            g.Add(time, idx);
            
            table[key].push_back(g);
        }
        else
        {
            for(auto& g : table[key])
            {
                if (g.name == genre)
                {
                    g.Add(time, idx);
                    return;
                }
            }
            
            Genre temp(genre);
            temp.Add(time, idx);
            table[key].push_back(temp);
        }
    }
    
    vector<vector<Genre>> table;
};


vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map m(genres.size());
    
    for (int i = 0; i < genres.size(); i++)
        m.insert(genres[i], plays[i], i);
    
    vector<Genre> gs;
    for(auto& v : m.table)
    {
        for(auto& g : v)
            gs.push_back(g);
    }
    
    sort(gs.begin(), gs.end(), [](Genre& a, Genre& b){
        return a.total > b.total;
    });
    
    for (auto g : gs)
    {
        answer.push_back(g.first_idx);
        if (g.second_idx >= 0)
            answer.push_back(g.second_idx);
    }
      return answer;
}