[ 프로그래머스 베스트 앨범 (Lv3) ] (C++)

프로그래머스의 베스트 앨범(Lv3) 문제이다.

[ 문제풀이 ]

문제에 조건 맞는 노래들을 선별해서 앨범에 들어갈 노래들을 정해야 하는 문제이다.

그럼 문제의 조건을 다시한번 보면서 우리가 알아둬야 할 사항에 대해서 부터 알아보고 시작해보자.

1. 속한 노래가 많이 재생된 장르를 가장 우선적으로 수록.

2. 장르 내에서 많이 재생된 노래를 우선적으로 수록.

3. 재생횟수가 같을 경우 번호가 낮은 노래를 우선적으로 수록.

문제에서 제시한 요구사항으로는 위와 같이 3개의 조건이 있다.

그럼 조건들을 하나씩 살펴보면서 노래를 어떻게 관리할지 생각해보자.

#1. 속한 노래가 많이 재생된 장르를 우선적으로 수록한다.

우리는 이 조건에서 모든 노래들을 "장르별"로 구분해야 할 필요가 있다는 것을 알 수 있다.

"장르별"로 구분하기 위해서는 각 노래들의 "장르명" 으로 구분을 하면 된다.

입력으로 주어지는 "classic", "pop"과 같이 이름으로 구분을 할 수가 있다.

즉 ! "우리는 장르별로 노래를 구분해 주어야 하는데, 이 때 구분하는 방법은 "장르명"으로 구분을 하면 된다.

그리고, 각 장르에 속하는 "노래들이 재생된 총 횟수"를 알고 있어야 한다.

#2. 장르 내에서 많이 재생된 노래를 우선적으로 수록한다.

첫 번째 조건에서 우리는 주어진 노래들을 장르별로 구분해 주었다.

그런데 이제는 "하나의 장르 안에서" 서로 다른 노래들 끼리 구분을 해주는 과정이다.

그럼 우리는 첫 번째 조건에서 장르별로 분류를 했으면 그 안에서는 또 "각 노래들이 재생된 횟수"를

알고 있어야 한다.

#3. 재생횟수가 같을 경우 번호가 낮은 노래를 우석적으로 수록한다.

두 번째 조건에서 하나 더 나아가서 "재생된 횟수가 동일할 경우, 번호가 낮은 노래를 우선적으로 수록"해야 한다는 것이다.

그럼 우리는 여기서 "노래들이 재생된 횟수" 뿐만 아니라, "수록된 노래의 번호"를 알고 있어야 한다.

우리는 위의 3가지 조건을 통해서 알아본, 우리가 알고 있어야 할 관리해야할 정보들은 다음과 같다.

1. 장르명

2. 각 장르별로, 수록된 노래들의 재생된 총 횟수

3. 각 장르 내에서, 수록된 노래 각각의 재생된 횟수

4. 각 장르 내에서, 수록된 노래 각각의 번호

이렇게 4개의 정보를 관리해야 한다.

따라서 본인은 위의 4가지 정보를 관리할 수 있도록 구조체를 하나 선언해주었다.

그리고 구조체 배열을 이용해서 노래들을 장르별로 관리해 주었다.

struct GENRE
{
    string Name;
    int Total_Play;
    vector<pair<int, int>> Music;
};
 
GENRE Arr[110];

위의 선언한 구조체가, 본인이 선언한 구조체이다.

구조체의 멤버변수로는 총 3개가 있다.

line3 : string Name

- 장르명을 관리하는 멤버변수이다. 우리는 가장 우선적으로 노래들을 장르별로 나눠야 했고, 나누기 위해서는 장르의 이름을

  알고 있어야 했다. 이 떄 사용되는 "장르의 이름"을 나타내는 멤버변수이다.

line4 : int Total_Play

- 장르별, 장르에 속한 모든 노래들의 총 재생 횟수를 관리하는 멤버변수이다.

  우리는 총 재생횟수가 많은 장르일수록 우선적으로 수록해야 하기 때문에, 이를 관리하기 위해서 사용되는 멤버변수이다.

line5 : vector<pair<int, int>> Music

- 장르 내에서, 수록된 노래들의 각각의 재생횟수와 번호를 한번에 관리하기 위한 벡터이다.

  하나의 장르에는 여러개의 노래가 들어갈 수 있고, 그 여러개의 노래는 모두 각자의 재생횟수와 번호를 가지고 있을 것이다.

  그 여러개의 노래들을 이 멤버변수에 계속해서 삽입하면서 관리하기 위한 멤버변수이다.

line8) 에서는 구조체 배열을 선언해 주었다. 배열의 크기는 110으로 잡아주었는데, 이는 문제에서 제시한 조건대로 장르의

최대 갯수는 100개라고 했으므로, 넉넉하게 110칸으로 설정해 주었다.

그럼 이제 이 구조체를 이용해서 본격적인 문제 풀이에 들어가보자.

가장 먼저, 주어진 장르들을 장르명으로 구분해줄 것이다. 그런데 ! 단순히 위에서 선언한 구조체 배열에 저장해줄 때, 생각해줘야 할 것이 하나 있다. 바로 "장르내에 속한 노래들의 총 재생횟수" 이다.

이 횟수를 삽입과 동시에 계산해 주었다.

    int Idx = 0;
    for (int i = 0; i < genres.size(); i++)
    {
        string Name = genres[i];
        bool Flag = false;
        for (int j = 0; j < Idx; j++)
        {
            if (Arr[j].Name == Name)
            {
                Flag = true;
                Arr[j].Total_Play = Arr[j].Total_Play + plays[i];
                Arr[j].Music.push_back(make_pair(plays[i], i));
                break;
            }
        }
        if (Flag == false)
        {
            Arr[Idx].Name = Name;
            Arr[Idx].Total_Play = plays[i];
            Arr[Idx].Music.push_back(make_pair(plays[i], i));
            Idx++;
        }
    }

위의 코드가 본인이 구현한 음악들을 장르별로 구분하는 부분이다.

line6 ~ 15)를 보게 되면, "이전까지 나왔던 장르들 중에서, 현재 내가 속한 장르가 있다면, 새로운 장르를 추가할 필요 없이,

해당 장르에 데이터만 추가해주는 과정이다. 여기서 "데이터"라는 것은, "총 재생횟수 , 노래의 재생횟수 , 노래의 번호" 를 의미한다.

반대로 line16)을 보게되면, "이전까지 나왔던 장르들 중에서, 내가 속한 장르가 없었던 경우" 를 의미한다.

즉 ! 새로운 장르를 추가적으로 선언해주는 과정이다.

위와 같이 장르별로 음악들을 장르별로 다 구분해주었으면, 이제는 조건에 맞는 노래들을 선발하기만 하면된다.

이를 위해서 본인은 정렬을 2번 사용해주었다.

1. 장르들 중에서, 우선순위를 갖는 장르별 순서로 정렬.

2. 장르 내에서, 우선순위를 갖는 노래별 순서로 정렬.

첫 번째로 장르별로 "총 재생된 횟수가 많은 노래가 더 높은 우선순위를 갖도록" 정렬 시켜 주었다.

두 번째로는 각 장르마다, 2개의 노래를 선발해 내기 위해서, 정렬을 시켜 주었다.

우리는 장르 내에 속한 노래들의 "재생횟수와 , 번호"를 vector에 하나로 관리해 주고 있다.

따라서 이 Vector를 정렬시켜 주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct GENRE
{
    string Name;
    int Total_Play;
    vector<pair<int, int>> Music;
};
 
GENRE Arr[110];
 
bool Cmp_Genre(GENRE A, GENRE B)
{
    if (A.Total_Play > B.Total_Play) return true;
    return false;
}
 
bool Cmp_Music(pair<int, int> A, pair<int, int> B)
{
    if (A.first > B.first) return true;
    else if (A.first == B.first)
    {
        if (A.second < B.second) return true;
        return false;
    }
    return false;
}
 
vector<int> solution(vector<string> genres, vector<int> plays) 
{
    vector<int> answer;
    int Idx = 0;
    for (int i = 0; i < genres.size(); i++)
    {
        string Name = genres[i];
        bool Flag = false;
        for (int j = 0; j < Idx; j++)
        {
            if (Arr[j].Name == Name)
            {
                Flag = true;
                Arr[j].Total_Play = Arr[j].Total_Play + plays[i];
                Arr[j].Music.push_back(make_pair(plays[i], i));
                break;
            }
        }
        if (Flag == false)
        {
            Arr[Idx].Name = Name;
            Arr[Idx].Total_Play = plays[i];
            Arr[Idx].Music.push_back(make_pair(plays[i], i));
            Idx++;
        }
    }
    
    sort(Arr, Arr + Idx, Cmp_Genre);
    for (int i = 0; i < Idx; i++)
    {
        sort(Arr[i].Music.begin(), Arr[i].Music.end(), Cmp_Music);
        if (Arr[i].Music.size() == 1) answer.push_back(Arr[i].Music[0].second);
        else
        {
            for (int j = 0; j < 2; j++)
            {
                answer.push_back(Arr[i].Music[j].second);
            }
        }
    }
    return answer;
}